Medium Problemsoptimizationlinear

Longest Increasing Subsequence

Given an array of integers, find the length of the longest subsequence whose values are strictly increasing. The chosen elements must keep their original relative order but need not be adjacent.

Do this lesson first: house robber

Example input

nums = [5, 2, 8, 6, 3, 6, 9, 7, 4] (the fixed array's first 9 entries)

Expected output

4

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i] = 1 + max over every j < i with nums[j] < nums[i] of dp[j], or 1 if no such j exists

Ask what came immediately before index i in the best subsequence that ends there. Either nothing does, so index i starts a chain of its own, or some earlier index j with a strictly smaller value is the previous chosen element, in which case dp[i] extends whichever qualifying j already holds the longest chain. Every qualifying j is a candidate to extend, compared rather than summed, since only one of them actually precedes index i in the chain that ends here.

dp[0] = 1 is the only declared base: with no index before 0, the first element is trivially a subsequence of length 1 all by itself, and it turns out to be read often, since most later values in this array are larger than nums[0] = 5. Every other index is a genuine compute cell, even the ones with no qualifying predecessor at all: dp[1] is exactly that case, since nums[0] = 5 is not smaller than nums[1] = 2, so dp[1] resolves to 1 on the strength of the same plus-one for standing alone, with no cell_read emitted, because there is nothing smaller before it to consult. Every other cell depends only on smaller indices, so filling left to right guarantees every predecessor that does qualify already holds a real value before it is read. Because the answer is whichever cell ends up largest, not necessarily the last one, the table also has to track that argmax as it fills, rather than simply reading off dp[8] at the end.

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

dp[0] = 1 is the only declared base: with no index before 0, the first element is trivially a subsequence of length 1 all by itself, and it turns out to be read often, since most later values in this array are larger than nums[0] = 5. Every other index is a genuine compute cell, even the ones with no qualifying predecessor at all: dp[1] is exactly that case, since nums[0] = 5 is not smaller than nums[1] = 2, so dp[1] resolves to 1 on the strength of the same plus-one for standing alone, with no cell_read emitted, because there is nothing smaller before it to consult. Every other cell depends only on smaller indices, so filling left to right guarantees every predecessor that does qualify already holds a real value before it is read. Because the answer is whichever cell ends up largest, not necessarily the last one, the table also has to track that argmax as it fills, rather than simply reading off dp[8] at the end.

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

1

2

3

4

3

longest-increasing-subsequence.ts

1function lengthOfLIS(nums) {
2 const dp = new Array(nums.length).fill(1);
3 let best = dp[0];
4 for (let i = 1; i < nums.length; i++) {
5 for (let j = 0; j < i; j++) {
6 if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
7 }
8 best = Math.max(best, dp[i]);
9 }
10 return best;
11}

Base caseComputedBeing readAnswer

The code, the trap, the variations

longest-increasing-subsequence.ts

1function lengthOfLIS(nums) {
2 const dp = new Array(nums.length).fill(1);
3 let best = dp[0];
4 for (let i = 1; i < nums.length; i++) {
5 for (let j = 0; j < i; j++) {
6 if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
7 }
8 best = Math.max(best, dp[i]);
9 }
10 return best;
11}

Where people go wrong

Reading the last cell, dp[n - 1], as the answer. The longest increasing subsequence can end anywhere in the array, so here it peaks at dp[6] = 4 while dp[8] only reaches 3; the real answer is the maximum over the whole table. A second, unrelated mistake is assuming the subsequence must be contiguous: it only has to preserve relative order, so 2, 3, 6, 9 counts even though 8 and 6 sit in between 2 and 3 in the array.

Return one such subsequence itself, not just its length.
Each cell would need to remember which earlier index it extended, so the sequence can be walked backward from the best cell once found; the length recurrence and the left-to-right order do not change at all.
Allow equal, non-decreasing values to extend a chain, not just strictly increasing ones.
The single comparison nums[j] < nums[i] loosens to nums[j] <= nums[i]; everything else, the plus-one, the max over qualifying j, and the argmax-over-the-table answer, stays exactly the same.

Longest Common Subsequence Edit Distance