Longest increasing subsequence
Given a list of integers nums, return the length of its longest strictly increasing
subsequence: elements taken in their original order, not necessarily adjacent, each larger than the one before.
Examples
| Input | Output | Why |
|---|---|---|
nums = [10,9,2,5,3,7,101,18] | 4 | 2, 3, 7, 18 (or 2, 5, 7, 101). |
nums = [7,7,7] | 1 | Equal values do not count as increasing. |
nums = [0,1,0,3,2,3] | 4 | 0, 1, 2, 3. |
Constraints
- 1 ≤ nums.length ≤ 2500
- −10⁴ ≤ nums[i] ≤ 10⁴
Hints
Hint 1
Fix where the subsequence ends. Let end[i] be the longest increasing subsequence that ends exactly at i.
Hint 2
end[i] is 1, or 1 + end[j] for an earlier j with nums[j] < nums[i]: take the best.
Hint 3
The answer is the maximum of end[i] over all i, not end[n − 1].
Where people lose marks
- Returning end[n − 1], which forces the subsequence to end at the last element.
- Using ≤ instead of <, which counts non-decreasing runs.
- Confusing subsequence with subarray: elements need not be adjacent.
Dry run on [10,9,2,5,3,7,101,18]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 8nums10091225334751016187end10·1·2·3·4·5·6·7
No earlier element is below 10: end[0] = 1.
-
Step 2 / 8nums10091225334751016187end1011·2·3·4·5·6·7
No earlier element is below 9: end[1] = 1.
-
Step 3 / 8nums10091225334751016187end101112·3·4·5·6·7
No earlier element is below 2: end[2] = 1.
-
Step 4 / 8nums10091225334751016187end10111223·4·5·6·7
5 can extend subsequences ending at 2: end[3] = 2.
-
Step 5 / 8nums10091225334751016187end1011122324·5·6·7
3 can extend subsequences ending at 2: end[4] = 2.
-
Step 6 / 8nums10091225334751016187end101112232435·6·7
7 can extend subsequences ending at 2, 5, 3: end[5] = 3.
-
Step 7 / 8nums10091225334751016187end10111223243546·7
101 can extend subsequences ending at 10, 9, 2, 5, 3, 7: end[6] = 4.
-
Step 8 / 8nums10091225334751016187end1011122324354647
18 can extend subsequences ending at 10, 9, 2, 5, 3, 7: end[7] = 4. The answer is the largest entry: 4.
How to think about it
Let end[i] be the length of the longest strictly increasing subsequence that ends at position i. Any
such subsequence either is nums[i] alone or extends one that ends at an earlier, smaller element, so
end[i] = 1 + max(end[j] : j < i, nums[j] < nums[i]), or 1 if there is no such j. Fill left to right;
the answer is the largest entry, since the best subsequence may end anywhere.
Complexity. Time O(n²) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def lis_length(nums):
end = [1] * len(nums) # end[i]: longest increasing run ending at i
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
end[i] = max(end[i], end[j] + 1)
return max(end)#include <algorithm>
#include <vector>
int solve(const std::vector<int>& nums) {
std::vector<int> end(nums.size(), 1); // longest ending at i
for (size_t i = 0; i < nums.size(); ++i)
for (size_t j = 0; j < i; ++j)
if (nums[j] < nums[i]) end[i] = std::max(end[i], end[j] + 1);
return *std::max_element(end.begin(), end.end());
}class Solution {
public int lisLength(int[] nums) {
int[] end = new int[nums.length]; // longest ending at i
int best = 0;
for (int i = 0; i < nums.length; i++) {
end[i] = 1;
for (int j = 0; j < i; j++)
if (nums[j] < nums[i]) end[i] = Math.max(end[i], end[j] + 1);
best = Math.max(best, end[i]);
}
return best;
}
}function lisLength(nums) {
const end = new Array(nums.length).fill(1); // longest ending at i
for (let i = 0; i < nums.length; i++)
for (let j = 0; j < i; j++)
if (nums[j] < nums[i]) end[i] = Math.max(end[i], end[j] + 1);
return Math.max(...end);
}fn solve(nums: &[i64]) -> i64 {
let mut end = vec![1i64; nums.len()]; // longest ending at i
for i in 0..nums.len() {
for j in 0..i {
if nums[j] < nums[i] {
end[i] = end[i].max(end[j] + 1);
}
}
}
*end.iter().max().unwrap()
}import Data.Array
solve :: [Int] -> Int
solve nums = maximum (elems end)
where
n = length nums
a = listArray (0, n - 1) nums
-- end ! i: longest increasing subsequence ending at i (a lazy array fills itself)
end = listArray (0, n - 1) [1 + maximum (0 : [end ! j | j <- [0 .. i - 1], a ! j < a ! i]) | i <- [0 .. n - 1]] :: Array Int IntVariants to try
- Do it in O(n log n) with the smallest-tail array and binary search (the next problem).
- Return the subsequence itself by storing each entry's predecessor.
- Count how many longest increasing subsequences there are.
Next problems
Longest increasing subsequence in O(n log n)
Keep, for each length, the smallest value an increasing subsequence of that length can end on; binary search does the rest.
Open the problem → Easy10 minThe cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem →Write a solution and run it against the real test table.
Keep going
Longest increasing subsequence in O(n log n)
Keep, for each length, the smallest value an increasing subsequence of that length can end on; binary search does the rest.
Open the problem → Easy10 minThe cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan a subset reach the target?
Decide whether some subset of positive integers adds up to exactly the target. A boolean array over totals, filled downwards for each number.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.