Problem overview
The method lengthOfLIS receives an array of integers, nums, and returns the length of its longest strictly increasing subsequence. A subsequence keeps some of the elements, possibly all or none, in their original order. It is strictly increasing when each element is larger than the one before, so equal values can't 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: [2, 3, 7, 101] works, and so does [2, 5, 7, 18]. No 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, because equal values don't increase.
The statement asks for O(n²) time and O(n) extra space.
Approach: the best subsequence that ends at each element
Checking every subsequence is out of the question: an array of 2500 elements has 2^2500 of them. Instead, solve a smaller question for each position. Let dp[i] be the length of the longest strictly increasing subsequence that ends with nums[i].
- Every
dp[i]is at least 1, becausenums[i]alone is a valid subsequence. - If an earlier element
nums[j](withj < i) is smaller thannums[i], thennums[i]can go after the best subsequence that ends atj. That gives a subsequence of lengthdp[j] + 1. - So
dp[i]is 1 plus the largestdp[j]over all suchj, or just 1 when no earlier element is smaller.
The longest subsequence can end anywhere, so the answer is the largest entry of dp, not necessarily the last one. For [10, 9, 2, 5, 3, 7, 101, 18] the table is:
[1, 1, 1, 2, 2, 3, 4, 4]
The 3 at index 4 has dp 2 (after the 2), and the 7 at index 5 has 3 (after 2, 3). Both 101 and 18 reach 4. For [1, 3, 6, 7, 9, 4, 10, 5, 6] the table is [1, 2, 3, 4, 5, 3, 6, 4, 5]: the last entry is 5, but the answer is 6, which ends at the 10. Returning the last entry would be wrong.
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. This lesson uses the simpler table.
Step by step
- Store the length of
numsinn. Both loops run over the indexes. - Create
dpwithnentries, all 1: each element alone is a subsequence of length 1. - Declare
bestwithlet, starting at 0. It changes as the loops run, so it can't beconst. - Loop
iover every index from left to right. When the loop reachesi, all earlier entries are final. - Loop
jover the earlier indexes, from 0 up to but not includingi. Fori = 0there are none, and the inner loop doesn't run. - Test
nums[j] < nums[i]. The comparison is strict because an equal value can't follow. - Update
dp[i]withMath.max(dp[i], dp[j] + 1). Over all validj, this keeps the best extension. - Update
bestwithMath.max(best, dp[i])after the inner loop, whendp[i]is final. - Return
bestafter the outer loop.
The solution in TypeScript
class Solution {
lengthOfLIS(nums: number[]): number {
const n = nums.length;
const dp: number[] = 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 TypeScript details:
new Array(n).fill(1)builds an array ofnempty slots and puts a 1 in each. The annotationnumber[]is checked by the compiler only; it disappears from the compiled JavaScript.constdoesn't freeze the array.dpis declared withconst, yetdp[i] = ...works:constonly stops you from assigning a different array to the namedp.bestis a plain number that gets reassigned, so it needslet.Math.maxtakes any number of arguments and returns the largest, which is a compact way to write "keep the better value".- Numbers are doubles. The values here stay small, so comparisons are exact. Comparing with
<is numeric because both sides are numbers; sorting is where JavaScript's default turns numbers into strings, and this solution doesn't sort.
Complexity
Time: O(n²). Every pair j < i is examined once, and there are n · (n - 1) / 2 pairs.
Space: O(n). The table dp has one entry per element; everything else is a few numbers.
Edge cases and common mistakes
- A single element.
[5]returns 1:dp[0]is 1, andbestbecomes 1. - Decreasing input.
[5, 4, 3, 2, 1]returns 1. Nonums[j] < nums[i]ever holds, so every entry stays 1. - Already increasing.
[1, 2, 3, 4]returns 4, with the table[1, 2, 3, 4]. - Equal values. Writing
<=instead of<would count the seven 7s as a subsequence of length 7, but the answer is 1. - Returning
dp[n - 1]. The longest subsequence doesn't have to end at the last element. That is whybesttracks the maximum. - Starting
dpat 0. Every element is a subsequence by itself, so the table starts at 1. - Mixing up subsequence and substring. The chosen elements need not be next to each other: in
[0, 1, 0, 3, 2, 3]the answer skips the second 0.
Testing
[10, 9, 2, 5, 3, 7, 101, 18]gives 4.[0, 1, 0, 3, 2, 3]gives 4.[7, 7, 7, 7, 7, 7, 7]gives 1.[5]gives 1.[5, 4, 3, 2, 1]gives 1.[1, 2, 3, 4]gives 4.[1, 3, 6, 7, 9, 4, 10, 5, 6]gives 6.
