Longest Increasing Subsequence
Given an integer array, return the length of the longest strictly increasing subsequence (elements need not be contiguous but must keep their relative order).
- 1 ≤ n ≤ 2500
- -10^4 ≤ nums[i] ≤ 10^4
- Subsequence, not subarray — choices are non-local
- Best sequence ending at i extends the best ending at some j < i with a smaller value
- n ≤ 2500 permits O(n^2)
Counting or optimizing over choices where a brute-force recursion revisits the same state signals DP: define the state so the answer to a state depends only on smaller states, then memoize or fill a table bottom-up. Subsequence (not subarray) wording, "number of ways", and "minimum/maximum over all choices" are the classic tells.
Let len[i] be the length of the longest increasing subsequence ending at index i, initially 1. For every j < i with nums[j] < nums[i], set len[i] = max(len[i], len[j] + 1). The answer is the maximum over all len[i]. Each entry depends only on earlier entries, so a double loop fills the table.
- Patience sorting keeps an array of the smallest tail for each length and binary searches each element into it, giving O(n log n).