Problem overview
The method lengthOfLIS(nums) receives an array of integers and returns the length of its longest strictly increasing subsequence. A subsequence is what remains after deleting some elements, possibly none, without reordering the rest. Strictly increasing means every element is larger than the one before it, so two equal values can never both be in it. Only the length is returned, not the subsequence itself.
For nums = [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4. One longest subsequence is [2, 3, 7, 101]; [2, 5, 7, 18] is another. No strictly increasing subsequence has 5 elements. For [0, 1, 0, 3, 2, 3] the answer is 4 ([0, 1, 2, 3]), and for seven 7s it is 1, since equal values don't increase.
The lesson asks for O(n²) time and O(n) extra space, where n is the length of nums.
Approach: the best subsequence ending at each index
An array of 2500 elements has 2 to the power 2500 subsequences, so checking them all is out of the question. Instead, solve smaller versions of the problem. Let dp[i] be the length of the longest strictly increasing subsequence that ends with nums[i].
Every dp[i] is at least 1, because nums[i] alone is a subsequence. To do better, look at every earlier index j < i. If nums[j] < nums[i], the element nums[i] can be added after the best subsequence that ends at j, which gives length dp[j] + 1. So dp[i] is 1 plus the largest dp[j] over all such j, or just 1 when no earlier element is smaller.
The longest subsequence can end anywhere, so the answer is the largest dp[i], not necessarily the last one. For the first example the table is:
nums: [10, 9, 2, 5, 3, 7, 101, 18]
dp: [1, 1, 1, 2, 2, 3, 4, 4]Here dp[6] = 4 for 101: the subsequence [2, 5, 7, 101] or [2, 3, 7, 101] ends there. For the second example, [0, 1, 0, 3, 2, 3], the table is [1, 2, 1, 3, 3, 4].
Take the entry for 7, at index 5, in the first example. The earlier elements are 10, 9, 2, 5 and 3. Of these, 2, 5 and 3 are smaller than 7, with dp values 1, 2 and 2. The largest is 2, so dp[5] = 2 + 1 = 3: for example [2, 5, 7]. The elements 10 and 9 are larger than 7, so they are skipped.
This also shows why the table stores the subsequence that ends at an index. To extend a subsequence you only need to know how long it is and what its last element is, and the last element is nums[j] itself.
Step by step
- Store the length of
numsinn. Both loops run over the indexes. - Create
dpwithnentries, all 1. No entry can be smaller, because each element alone counts. - Declare
bestwithlet, starting at 0. It changes as the loop goes, so it can't be aconst. - Loop over
ifrom 0 ton - 1. Eachdp[i]needs only entries before it, which are final by then. - Loop over every earlier index
jfrom 0 toi - 1. Fori = 0this loop doesn't run. - Test
nums[j] < nums[i]. It is strict: an equal value can't follow another. - Update
dp[i]to the larger of its current value anddp[j] + 1. Over all validj, this keeps the best. - Update
bestafter the inner loop, whendp[i]is final. - Return
best.
The solution in JavaScript
class Solution {
lengthOfLIS(nums) {
const n = nums.length;
const dp = new Array(n).fill(1);
let best = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
best = Math.max(best, dp[i]);
}
return best;
}
}
Some JavaScript details:
constdoes not freeze the array.const dpmeans the name can't be reassigned, butdp[i] = ...changes an element without any problem.Math.maxtakes any number of arguments. Here it gets two: the current value and the candidate. It returns the larger number.- Numbers compare numerically.
nums[j] < nums[i]works on numbers, including negative ones. Sorting is different:[10, 9, 1].sort()gives[1, 10, 9], becausesort()without a comparator orders values as strings. This solution never sorts.
Complexity
Time: O(n²). Every pair j < i is looked at exactly once, and there are n · (n - 1) / 2 pairs. For 2500 elements that is about three million comparisons.
Space: O(n). The table dp has one entry per element.
A faster O(n log n) method exists. It keeps, for each length, the smallest value an increasing subsequence of that length can end with, and places each element in that list with a binary search. It gives the same answers on the examples (4, 4 and 1), but the table approach is simpler to write and to check.
Edge cases and common mistakes
- Using
<=. Withnums[j] <= nums[i]the seven 7s would give 7 instead of 1. The subsequence must be strictly increasing. - Returning the last
dpentry. For[3, 1, 2]the table is[1, 1, 2]and the answer is 2, but for[1, 2, 3, 0]the last entry is 1 while the answer is 3. The best subsequence can end at any index. - Starting
dpat 0. A single element is a subsequence of length 1, so[5]must return 1. - Confusing subsequence with substring. The chosen elements don't need to be next to each other:
[0, 1, 2, 3]in the second example skips over the second 0 and the 3 between them. - A decreasing array.
[4, 3, 2, 1]returns 1: no element can follow another.
Testing
[10, 9, 2, 5, 3, 7, 101, 18]gives4.[0, 1, 0, 3, 2, 3]gives4.[7, 7, 7, 7, 7, 7, 7]gives1.[5]gives1.[1, 2, 3, 4]gives4.[4, 3, 2, 1]gives1.[3, 1, 2]gives2.
