Longest Increasing Subsequence
MediumGiven an integer array nums, return the length of its longest strictly increasing subsequence. A subsequence keeps the original order of the elements but can skip some of them.
Example 1
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18] Output: 4
One longest increasing subsequence is [2, 3, 7, 101].
Example 2
Input: nums = [7, 7, 7, 7] Output: 1
The values have to strictly increase, so the longest subsequence is a single element.
Constraints
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4
Approach
The classic solution defines dp[i] as the length of the longest increasing subsequence ending at index i and checks every earlier index to fill it in. That's correct but takes O(n²) time.
A faster method keeps tails, where tails[k] is the smallest value that can end an increasing subsequence of length k + 1. A smaller ending value is always better, because it leaves more room for later numbers. tails stays sorted, so for each number x you can binary search for the first entry that's greater than or equal to x. If there isn't one, x extends the longest subsequence so far. Otherwise, x replaces that entry, which keeps the ending value for that length as small as possible. The length of tails at the end is the answer.
Steps
- Start with an empty array,
tails. - For each
xinnums, find the first indexiintailswheretails[i] >= x. - If there's no such index, append
x. Otherwise, settails[i] = x. - Return the length of
tails.
Complexity
- Time:
O(n log n). Each number costs one binary search. - Space:
O(n).tailscan grow to the length ofnums.
Common mistakes
- Treating
tailsas an actual subsequence. Its length is correct, but its contents can mix values from different subsequences. - Searching for the first value strictly greater than
xinstead of greater than or equal to it. Equal values would then extend the sequence, which breaks the strictly increasing rule.
Related questions
Find the longest increasing subsequence.Find the longest alternating subsequence.Longest Increasing Path in a MatrixRelated courses


