Problem overview
The method lengthOfLIS receives a list 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 and deletes the rest. It is strictly increasing when every element is larger than the one before it, so two equal values can't both belong to it. Only the length is returned, not the subsequence.
For nums = [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4. The subsequence [2, 3, 7, 101] qualifies, and so does [2, 5, 7, 18]. No increasing subsequence has 5 elements. For [0, 1, 0, 3, 2, 3] the answer is also 4, from [0, 1, 2, 3]. For [7, 7, 7, 7, 7, 7, 7] it is 1, because equal values don't increase.
The statement asks for O(n²) time and O(n) extra space, where n is the length of nums.
Approach: the best subsequence ending at each element
A list of n elements has 2 to the power n subsequences, so trying them all is out of the question for a list of 2,500 elements. The lesson solves smaller versions of the problem instead.
Let dp[i] be the length of the longest strictly increasing subsequence that ends with nums[i]. Fixing the last element is the key: it makes the question about nums[i] easy to answer from earlier answers.
- Every
dp[i]is at least 1, becausenums[i]alone is such a subsequence. - For an earlier index
j < iwithnums[j] < nums[i], the elementnums[i]can be appended to the best subsequence ending atj. That gives lengthdp[j] + 1. - So
dp[i]is 1 plus the largestdp[j]among thosej, or just 1 if no earlier element is smaller.
The longest subsequence can end anywhere, so the answer is the largest dp[i], not necessarily the last one.
Here are the finished tables for the examples:
nums = [10, 9, 2, 5, 3, 7, 101, 18]
dp = [1, 1, 1, 2, 2, 3, 4, 4]
nums = [0, 1, 0, 3, 2, 3]
dp = [1, 2, 1, 3, 3, 4]
nums = [7, 7, 7, 7, 7, 7, 7]
dp = [1, 1, 1, 1, 1, 1, 1]
In the first list, dp[5] is 3 because 7 can follow 3, which ends a subsequence of length 2 ([2, 3]). Then 101 extends that to 4. The 18 also reaches 4, through 7. In the second list the answer 4 sits at the last index, but in [5, 4, 3, 2, 1] every entry is 1 and the answer comes from the first.
The statement mentions a faster O(n log n) method: keep, for each length, the smallest value an increasing subsequence of that length can end with, and place each element in that list with a binary search. This lesson practises the table, which is the idea you reuse in many other dynamic programming problems.
Step by step
- Store the length of
numsinn. Both loops run over the indexes. - Create
dpas[1] * n. Every element is a subsequence of length 1 by itself, so no entry is below 1. - Start
bestat 0. It holds the largest length found so far. - Loop over
iinrange(n). Eachdp[i]needs only entries to its left, which are complete by the time the loop reachesi. - Loop over
jinrange(i), the indexes beforei. Only elements beforenums[i]can come before it in a subsequence. Fori = 0the inner loop doesn't run. - Check
nums[j] < nums[i]. The test is strict, so equal values are skipped. - Update
dp[i]withmax(dp[i], dp[j] + 1). Over all validj, this keeps the best extension. - After the inner loop, update
bestwithmax(best, dp[i]). This line sits inside the outer loop, at the same indentation as the innerfor, becausedp[i]is final only after everyjwas examined. - Return
bestafter both loops.
The solution in Python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [1] * n
best = 0
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
best = max(best, dp[i])
return best
Python details worth a closer look:
range(i)yields 0 up toi - 1, and it is empty wheniis 0. That is exactly the set of earlier indexes.maxwith two arguments returns the larger one. Here it replaces anifthat compares and assigns.- Why
bestinstead ofmax(dp). The solution tracksbestas it goes, which avoids a second pass. Returningmax(dp)after the loops gives the same result for a non-empty list. For an empty listmax(dp)raisesValueError(max() iterable argument is empty), while this solution returns 0. - Indentation decides what repeats. Moving the
best = max(best, dp[i])line out of the outer loop would read only the lastdp[i]and be wrong. Moving it into the inner loop would never run fori = 0, so[5]would return 0.
Complexity
Time: O(n²). The two loops look at each pair j < i once, which is n · (n - 1) / 2 pairs. For 2,500 elements that is about 3 million comparisons.
Space: O(n). The table has one entry per element, and the rest are single variables.
Edge cases and common mistakes
- Using
<=instead of<. That counts equal values as increasing.[7, 7, 7, 7, 7, 7, 7]would then return 7 instead of 1. - Returning
dp[n - 1]. The best subsequence need not end at the last element. For[1, 2, 3, 4, 0]the last entry is 1, but the answer is 4. - Starting
dpat 0. Then each element alone is counted as length 0, and every answer is one too small. - Confusing a subsequence with a subarray. A subsequence may skip elements. In
[0, 1, 0, 3, 2, 3],[0, 1, 2, 3]skips the second 0 and the 3. - A single element.
[5]returns 1:dpis[1]and the inner loop never runs. - Decreasing lists.
[5, 4, 3, 2, 1]returns 1, since nonums[j] < nums[i]is ever true.
Testing
nums = [10, 9, 2, 5, 3, 7, 101, 18]gives4.nums = [0, 1, 0, 3, 2, 3]gives4.nums = [7, 7, 7, 7, 7, 7, 7]gives1.nums = [5]gives1.nums = [5, 4, 3, 2, 1]gives1.nums = [1, 2, 3, 4]gives4.nums = [1, 3, 2, 3]gives3.
