Longest Increasing Subsequence
Keep the smallest possible tail for each subsequence length.
Approach
The O(n²) DP sets dp[i] to the best subsequence ending at i. The elegant O(n log n) approach maintains a 'tails' array where tails[k] is the smallest tail of an increasing subsequence of length k+1; binary search each number's insertion point. The tails length is the answer.
Time complexity
O(n log n)
Space complexity
O(n)
Common mistake
Thinking the tails array is an actual subsequence — it isn't, but its length is correct.
See it run, step by step
Generate an interactive lesson for Longest Increasing Subsequence — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Longest Increasing Subsequence