Problem overview
The function length_of_lis receives a vector of integers, nums, and returns the length of its longest strictly increasing subsequence. A subsequence is what remains after deleting some elements, possibly none, without reordering the others. "Strictly increasing" means every element is larger than the one before it, so two equal values can't both be in it. Only the length is returned, not the subsequence.
For nums = [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4: [2, 3, 7, 101] and [2, 5, 7, 18] both qualify, and no subsequence has 5 elements. For [0, 1, 0, 3, 2, 3] the answer is 4, from [0, 1, 2, 3]. For [7, 7, 7, 7, 7, 7, 7] it is 1, because equal values don't increase.
The lesson asks for O(n²) time and O(n) extra space.
Approach: the best subsequence ending at each index
A vector of n elements has 2^n subsequences, so with up to 2,500 elements, trying them all is out of the question. 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, since nums[i] alone is a valid subsequence. To do better, look at every earlier index j < i. When nums[j] < nums[i], the element nums[i] can be appended to the best subsequence that ends at j, which gives length dp[j] + 1. So dp[i] is 1 plus the largest dp[j] among the smaller earlier elements, or just 1 when there are none.
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]
Take the 7 at index 5: the smaller elements before it are 2, 5 and 3, with dp values 1, 2 and 2, so dp[5] is 2 + 1 = 3. The largest entry is 4, which is the answer. Because the table is filled from left to right, every dp[j] with j < i is final by the time dp[i] is computed.
A faster O(n log n) method exists: 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 version.
Step by step
- Store the length.
n = nums.len()bounds both loops. - Create
dpwithvec![1; n]:nones, because each element alone is a subsequence of length 1. Rust works out that the entries arei32from how they are used, since they flow intobestandbestis the return value. - Create
best, mutable, starting at 0. It tracks the longest length found so far. - Loop over every index
iwith0..n, which stops beforen. - Loop over the earlier indexes
jwith0..i. Fori = 0the range is empty and the loop doesn't run. - Check
nums[j] < nums[i]. The comparison is strict, so an equal value can't extend a subsequence. - Update
dp[i]to the larger of its current value anddp[j] + 1, using themaxmethod. Across all validjthis keeps the best. - Update
bestafter the inner loop, oncedp[i]is final. - Return
bestwithout a semicolon.
The solution in Rust
impl Solution {
fn length_of_lis(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut dp = vec![1; n];
let mut best = 0;
for i in 0..n {
for j in 0..i {
if nums[j] < nums[i] {
dp[i] = dp[i].max(dp[j] + 1);
}
}
best = best.max(dp[i]);
}
best
}
}
The Rust details worth a closer look:
a.max(b). Integers have amaxmethod that returns the larger of the two values. It replaces anifthat compares and assigns.- Type inference. Neither
vec![1; n]norlet mut best = 0names a type. Both are fixed by the function's return type,i32, becausebestis returned and takes its values fromdp. - Indexing with
usize.ncomes fromlen(), so it is ausize, and so areiandj. That is exactly what a vector's index operator expects, so no casts are needed. - Index loops.
for i in 0..nwithnums[i]is the direct form here, because the inner loop needs the positionsj < i. The code readsdp[j]while writingdp[i], which is fine because each statement is a separate indexing operation. - Final expression.
besthas no semicolon, so it is the function's result.
Complexity
Time: O(n²). Every pair j < i is looked at once, and there are n · (n - 1) / 2 pairs. Each look is a comparison and possibly a max, which takes constant time.
Space: O(n). The dp vector holds one integer per element, and the other variables are single numbers.
Edge cases and common mistakes
- Equal values. Writing
<=instead of<would count[7, 7, 7, 7, 7, 7, 7]as an increasing run of 7. The correct answer is 1. - Returning the last entry. The longest subsequence can end anywhere. For
[1, 2, 3, 0]the table is[1, 2, 3, 1]: the last entry is 1, but the answer is 3. Track the maximum, asbestdoes. - Treating
dp[i]as the best answer for the firstielements. It is the best that ends atnums[i]. Mixing the two meanings breaks the transition, because only subsequences ending belownums[i]can be extended by it. - Decreasing input. For
[5, 4, 3, 2, 1]nonums[j] < nums[i]ever holds, so every entry stays 1 and the answer is 1. - Starting
bestat 1 or atdp[0]. Starting at 0 and taking the maximum in the loop is simplest. An empty vector then returns 0 without a panic, though the constraints promise at least one element.
Testing
[10, 9, 2, 5, 3, 7, 101, 18]gives 4, withdp = [1, 1, 1, 2, 2, 3, 4, 4].[0, 1, 0, 3, 2, 3]gives 4, withdp = [1, 2, 1, 3, 3, 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, 2, 3, 0]gives 3, withdp = [1, 2, 3, 1].[4, 10, 4, 3, 8, 9]gives 3, withdp = [1, 2, 1, 1, 2, 3].
