Longest Increasing Subsequence
O(n^2) DP then the O(n log n) trick.
What an LIS Is
A subsequence keeps order but skips elements. The longest increasing one is the longest such run that strictly rises.
a = [3, 1, 4, 1, 5, 9, 2]Subsequence, Not Subarray
Unlike a subarray, an LIS need not be contiguous. You may jump over smaller numbers to keep the chain growing.
All lessons in this course
- Memoization vs Tabulation
- Define State and Transition
- Climbing Stairs & Coin Combinations
- Longest Increasing Subsequence