DPDynamic Programming
Longest Increasing Subsequence (O(n²))
Find the length of the longest strictly increasing subsequence — O(n²) DP or O(n log n) with patience sorting.
3
0
1
1
8
2
2
3
5
4
4
5
9
6
6
7
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1/30dp[i] = length of the longest increasing subsequence ending exactly at i. Every element alone is a subsequence of length 1.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Longest Increasing Subsequence →
1dp[i] = 1 for all i // LIS ending at i2for i in 1 .. n-1:3 for j in 0 .. i-1:4 if a[j] < a[i] and dp[j] + 1 > dp[i]:5 dp[i] = dp[j] + 1; prev[i] = j6answer = max(dp); reconstruct via prevVariables
n8
Complexity
best O(n log n)
avg O(n log n)
worst O(n log n)
space O(n)
Speed