Longest Increasing Subsequence
O(n^2) DP over predecessors, or O(n log n) with patience sorting and binary search.
Decision · step 3 of 10DP in One Row: Longest increasing subsequence
9: nothing before it is smaller, so no chain can take it. len[1] = 1.
What you will see
Arrows from every smaller earlier element; or a tails array that binary search updates.
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).
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Table cells announce their state and value; each step announces which cells were read and the value written.
Reduced motion: Dependency arrows appear statically and the cell value crossfades.
Before this
Variants
- O(n^2) DP Best ending at each index.
- Patience Sorting Binary search into the tails array.
Taught by the same lesson
DP in One Row covers these too, in the same run.