Longest Increasing Subsequence
Keep the smallest possible tail for each subsequence length.
Tails Trace
Problem
Given an array of integers, determine the maximum number of elements that can form a strictly increasing subsequence while preserving their original order. The chosen elements do not need to be adjacent, and only the length of the best subsequence is required.
Examples
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Input: nums = [0,1,0,3,2,3]
Output: 4
The Goal
Return the length of the longest strictly increasing subsequence of nums. A subsequence keeps the original order but can skip numbers.
For [10, 9, 2, 5, 3, 7, 101, 18], one longest is [2, 3, 7, 101], so the answer is 4.
The usual DP is O(n²). Keeping one sorted list and binary-searching it brings that to O(n log n).
Skip, but don't reorder
Pick numbers in their original order, each bigger than the one before. Numbers in between can be skipped.
[2, 3, 7, 101] skips 10, 9, 5 and 18.
Key Idea: Keep the Smallest Tail for Each Length
Let tails[k] be the smallest number that can end an increasing run of length k + 1 so far. A smaller tail is better, since more numbers can follow it.
tails is always sorted. For each new x, find the first tail that isn't smaller than x. Replace it with x, or append x if every tail is smaller.
The answer is how long tails gets.
x takes the first tail that's at least x.
[2, 5] becomes [2, 3] after 3
The Algorithm
tails = []
for x in nums:
lo, hi = 0, len(tails)
while lo < hi:
mid = (lo + hi) // 2
if tails[mid] < x:
lo = mid + 1
else:
hi = mid
if lo == len(tails):
tails.append(x)
else:
tails[lo] = x
return len(tails)The search finds the first tail >= x, like Python's bisect_left. hi starts at len(tails), so the slot past the end can be the answer.
| Approach | What it keeps | Time |
|---|---|---|
| DP over endings | The longest run ending at each index | O(n^2) |
| Tails and binary search | The smallest tail for each length | O(n log n) |
Walkthrough
Run it on [10, 9, 2, 5, 3, 7, 101, 18].
10, then 9, then 2 each replace the only tail, leaving [2]. 5 appends, and 3 replaces 5: [2, 3]. 7 and 101 append: [2, 3, 7, 101]. 18 replaces 101.
The answer is 4. The final tails, [2, 3, 7, 18], is a real subsequence here, but [10, 20, 1] ends with [1, 20], which isn't one.
Checkpoint · predict the next step
Step 12 of 38 on the stage: Place 5. It goes at the first tail that isn't smaller, from lo = 0 to hi = 1, the slot past the end.
lo on 2 (index 0) · hi past the end · placing 5 · x 5 · len(tails) 1
Pitfalls
tailsisn't the subsequence. Only its length is the answer.- Search for the first tail
>= x. With> x, equal numbers would count as increasing:[7, 7, 7, 7]would give 4, not 1. - Replacing never shortens
tails, so a longer run found earlier still counts. - To return the subsequence itself, also record which number each one followed.
After the whole input, tails = [2, 3, 7, 18]. What does that guarantee?
Complexity
Each of the n numbers does one binary search over tails, at most log n steps, then one write. That's O(n log n) time.
tails grows to the answer's length, at most n, so extra space is O(n).
A binary search per number
- Numbers placedEach once.O(n)
- Binary searchtails is sorted.O(log n)
- tailsUp to one slot per number.O(n)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n log n) | 33 | 664 | 10K | 132.9K |
| O(n) | 10 | 100 | 1K | 10K |
A sorted list of tails turns each step from a scan into a search.
In short
The O(n²) DP sets dp[i] to the best subsequence ending at i. The elegant O(n log n) approach maintains a 'tails' array where tails[k] is the smallest tail of an increasing subsequence of length k+1; binary search each number's insertion point. The tails length is the answer.
Common mistake
Thinking the tails array is an actual subsequence — it isn't, but its length is correct.