Three questions#
Every dynamic programming solution is the answer to three questions.
- What is the state? Something small enough to enumerate, that captures everything you need to know about a partial answer.
- What is the recurrence? How the answer at one state is built from smaller ones.
- In what order do you fill it in? Every state must be computed before anything that depends on it.
If you can answer all three, the code writes itself. If you are stuck, one of the three is wrong, and usually it is the state.
Longest increasing subsequence, the honest way#
State: dp[i] is the length of the longest increasing subsequence that ends at index i. Ending at a specific index is what makes the state usable, the same trick Kadane's algorithm uses.
Recurrence: to end at i, the previous element must be at some j < i with a[j] < a[i]. So
dp[i] = 1 + max(dp[j] for j < i where a[j] < a[i])
and dp[i] = 1 when no such j exists, because the element alone is a subsequence.
Order: left to right. The answer is the largest value anywhere in dp, not dp[n-1], because the best subsequence does not have to end at the last element.
That is O(n^2), which is fine for a few thousand elements and too slow for 100000.
The fast version, and why it works#
Keep an array tails, where tails[k] is the smallest possible value that ends an increasing subsequence of length k + 1 seen so far.
That array is always sorted. For each new element, binary search for the first entry that is greater than or equal to it, and overwrite it. If there is none, append. The length of tails at the end is the answer.
Why overwriting is safe: a subsequence of the same length ending in a smaller value is never worse. Anything that could be appended to the old one can be appended to the new one too.
Note what tails is not: it is not the subsequence itself. Its contents at any moment may not be a real subsequence of the input. Only its length is meaningful. That is O(n log n).
Top down or bottom up#
Memoised recursion and a filled table compute the same thing. Recursion is easier to write from the recurrence and risks a deep stack. A table is easier to reason about for memory, and lets you drop to a rolling row when only the previous row matters.
Common mistakes#
- Returning
dp[n-1]when the answer is the maximum over the whole table. - Confusing subsequence with subarray. A subsequence may skip elements, a subarray may not.
- Using
>=where the problem says strictly increasing, which quietly allows duplicates.