MediumLongest strictly increasing subsequence — dp[i] = best run ending at i.
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but does not have to be contiguous.
Walkthrough
try:
Longest strictly increasing subsequence (elements need not be adjacent). dp[i] = best subsequence ending at i.
0
1
2
3
4
5
6
7
nums
10
9
2
5
3
7
101
18
dp
1
1
1
1
1
1
1
1
best = 1
i (extending)j (candidate tail)
1
function lengthOfLIS(nums) {
2
const n = nums.length;
3
const dp = new Array(n).fill(1);
◄
4
let best = 1;
5
for (let i = 1; i < n; i++) {
6
for (let j = 0; j < i; j++) {
7
if (nums[j] < nums[i]) {
8
dp[i] = Math.max(dp[i], dp[j] + 1);
9
}
10
}
11
best = Math.max(best, dp[i]);
12
}
13
return best;
14
}
dp = [1, 1, 1, 1, 1, 1, 1, 1]
step 0 / 54
line 3
dp[i] = LIS ending at i
dp[i] is the length of the longest increasing subsequence that ENDS at index i. Every element alone is a subsequence of length 1, so start all at 1.
Intuition
Define dp[i] = the length of the longest increasing subsequence that ENDS exactly at index i. Anchoring on the last element is what makes the recurrence work.
Every element alone is a subsequence of length 1, so every dp[i] starts at 1.
To extend to i, look back at every earlier j: if nums[j] < nums[i], then the run ending at j can be extended by nums[i], giving a candidate of dp[j] + 1. Take the best.
The answer is not dp[n−1] but the MAXIMUM dp value anywhere — the longest run may not end at the last element.