Longest Increasing Subsequence
Find how long the longest strictly increasing subsequence of the integer array nums is; its elements do not have to sit next to each other.
Examples
One longest run is [2,3,7,101]. It ends at index 6, so dp[7] is not the answer.
[0,1,2,3] is the longest strictly increasing subsequence.
Strictly increasing means equal values cannot extend each other.
Problem Understanding
A subsequence is derived by deleting some or no elements without changing the order.
Example: [10, 9, 2, 5, 3, 7, 101, 18]
- One LIS:
[2, 3, 7, 101] - Length: 4
Algorithm Strategy
dp[i] is the length of the longest strictly increasing subsequence that ends at index i.
Fixing the ending is what makes this decomposable: a run ending at i is some run ending at an earlier j with nums[j] < nums[i], plus nums[i] itself.
Recurrence: for every j < i with nums[j] < nums[i],
dp[i] = max(dp[i], dp[j] + 1)
Base case: every cell starts at 1 — a single element is already an increasing subsequence.
The answer is max(dp), not dp[n-1]. The longest run can end anywhere.
Interactive Visualization
Two rows: the value at each index, and the length of the longest run ending there. On every comparison the earlier index lights in both rows at once, so nums[j] < nums[i] and dp[j] + 1 read as one thing.
Watch the last frame: the answer cell is index 6, not index 7 — which is why the return is max(dp).
Dry Run
nums = [10, 9, 2, 5]
| i | Val | Default | j (Comparing) | Extend? | New dp[i] |
|---|---|---|---|---|---|
| 0 | 10 | 1 | - | - | 1 |
| 1 | 9 | 1 | j=0 (10) | No (9<10) | 1 |
| 2 | 2 | 1 | j=0, j=1 | No | 1 |
| 3 | 5 | 1 | j=2 (2) | Yes (5>2) | dp[2]+1 = 2 |
Edge Cases & Common Mistakes
Details matter:
Strictly increasing. The test is
nums[j] < nums[i], not<=. On [7,7,7,7,7] nothing extends anything and the answer is 1.Return max(dp), not dp[n-1]. The longest run can end anywhere. This is the single most common wrong answer to this problem.
Every cell starts at 1, not 0. A single element is already an increasing subsequence of length 1, and a table of zeros would report 0 for an array that has one.
Solution
Every ending, against every earlier one — the lines light up as the figure above steps.
Longest Increasing Subsequence Code
1var lengthOfLIS = function(nums) {2 const n = nums.length;3 const dp = new Array(n).fill(1);4 for (let i = 0; i < n; i++) {5 for (let j = 0; j < i; j++) {6 if (nums[j] < nums[i]) {7 dp[i] = Math.max(dp[i], dp[j] + 1);8 }9 }10 }11 return Math.max(...dp);12};