Longest Increasing Subsequence
O(n^2) DP over predecessors, or O(n log n) with patience sorting and binary search.
DP in One Row: Longest increasing subsequence
9: nothing before it is smaller, so no chain can take it. len[1] = 1.
Cost
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(n)
Quadratic variant is O(n^2).
Before this
Variants
- O(n^2) DP
- Patience Sorting
Taught by the same lesson
DP in One Row covers these too, in the same run.