DP: Longest Increasing Subsequence
Medium+90 XPFind the longest run of increasing numbers (not necessarily next to each other) with a dp[] table.
No visualization loaded.
Watch
—
Press Run to begin.
Given a list of numbers, find the longest chain you can pick — left to right — where each picked number is bigger than the last. The picks don't have to be next to each other, just in order. The idea: for each position i, compute dp[i] = the longest increasing chain that ENDS exactly at i. To get it, look at every earlier position j with a smaller value; you can hook onto its chain. dp[i] = 1 + the best dp[j] you can extend (or just 1 if nothing is smaller). The answer is the biggest dp value anywhere.
▸What does 'subsequence' mean here — isn't that just a chunk of the list?
No — a subsequence keeps the ORDER but can skip elements. From [3,1,4,1,5] you may pick 3,4,5 (skipping the 1's). A 'substring'/'subarray' would have to be contiguous; a subsequence can jump over numbers as long as it doesn't reorder them.
▸Why define dp[i] as 'ending AT i' instead of 'best so far'?
Pinning the chain's end to i makes the recurrence clean: a chain ending at i must come from some earlier chain ending at a smaller value, then step to i. If you instead tracked 'best so far,' you couldn't tell which chains are still extendable. So we compute every dp[i], then take the max at the end.
▸What are the highlighted cells doing during the inner scan?
For the current index i, we walk every earlier index j. If nums[j] < nums[i] (green), the chain ending at j can be extended by i, giving dp[j]+1 — a candidate. If nums[j] ≥ nums[i] (greyed out), it can't extend, so we skip it. dp[i] is 1 plus the best extendable candidate.
▸Why is the answer the maximum of dp[], not dp of the last element?
The longest chain can end anywhere, not necessarily at the last number. In [2,5,1,3], the best chain is 2,5 (length 2) ending at index 1, or 1,3 ending at index 3 — the last element's dp isn't the winner. So we scan all dp values and take the largest.
How the work grows
O(n²) is slow — explodes on big inputs. For each of the n positions you scan all earlier positions, so n×n/2 ≈ O(n²) comparisons. (A cleverer patience-sorting version reaches O(n log n), but the table version shown here is the clearest to learn.) Memory is one dp value per element.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.