← All patternsLongest Increasing Subsequence · template
Pattern · Dynamic Programming
Longest Increasing Subsequence
dp[i] is the longest increasing run ending at i; a patience-sorting version with binary search gets O(n log n).
Time O(n log n) · Space O(n)
Taught in Module 31: DP on Strings and Sequences
Think of it like this
Stacking cards into piles where each card goes on the leftmost pile whose top is bigger: the number of piles is the answer.
Clues that point here
- → Longest increasing (or non-decreasing) subsequence
- → Chains of pairs
- → Russian doll envelopes
- → Elements may be skipped but order kept
Not this pattern when
- ✕ The run must be contiguous (one pass suffices)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
List<Integer> tails = new ArrayList<>(); // tails[k] = smallest tail of an increasing run of length k+1
for (int x : nums) {
int i = Collections.binarySearch(tails, x);
if (i < 0) i = -(i + 1); // insertion point
if (i == tails.size()) tails.add(x); else tails.set(i, x);
}
return tails.size();Common versions
- Longest increasing subsequence
- Number of LIS
- Russian doll envelopes
- Maximum length of pair chain