Sign in to watch this lesson
Algorithms - Dynamic Programming · 4:40
Longest Increasing Subsequence
Given a sequence of prices, find the longest subsequence that rises strictly. We start with the natural O(n^2) DP over the best length ending at each position, whose back-arrows trace both answers of the example, then switch to the tails array, which stays sorted so lower_bound updates exactly one slot per price in O(log n). The tails are not the answer, so we restore a real subsequence from the slot each price landed in, and measure both methods on this Mac.
You will learn
- Write the O(n^2) DP d[i] = 1 + max d[j] over earlier smaller values, and restore an answer with parent pointers
- Explain why the array of smallest tails stays sorted, so each new value changes exactly one slot found by lower_bound
- Restore an actual LIS in O(n log n) from the slot each value landed in, and know why the tails array itself is not an answer
- Adapt the method to non-decreasing subsequences (upper_bound) and to counting LIS with a Fenwick tree