Dynamic Programming · LC #300
Longest Increasing Subsequence
Maintain a `tails` array where `tails[i]` is the smallest tail of all increasing subsequences of length `i+1`. Binary search each element into `tails` to achieve O(n log n) time.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an integer array `nums`, return the length of the longest strictly increasing subsequence.
Sample I/O
Input: nums = [10,9,2,5,3,7,101,18] Output: 4 ([2,5,7,101]) Input: nums = [0,1,0,3,2,3] Output: 4
Intuition
How to Think About It
Intuition
Each number either extends the longest subsequence found so far (append) or improves the ending value of some existing subsequence (replace). The key insight is that replacing with a smaller tail value never worsens the count but leaves room for longer subsequences in the future.
Core Concept
Patience sorting variant: `tails` is always sorted. For each number, binary search for the leftmost tail ≥ number. If found, replace it (keeping the count the same but improving the tail). If not found, append (length grows by 1). Final LIS length = tails.length.
When to use
Any problem asking for the length of the longest strictly (or non-strictly) increasing subsequence, or problems reducible to LIS (e.g., longest chain, Russian dolls).
When NOT to use
When you need to reconstruct the actual subsequence - the tails array itself is not the LIS; use a parent-pointer table instead. Not applicable to non-contiguous maximum sum problems.
Key Insights
What to Know Cold
- `tails` is always strictly sorted, enabling binary search with `bisect_left`.
- Replacing does not change `tails.length` - it only improves future extension potential.
- The O(n²) DP alternative: `dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i])`, simpler but slower.
- For non-strictly increasing (≤ instead of <), use `bisect_right` instead of `bisect_left`.
- Russian Doll Envelopes (LC 354) reduces to LIS after sorting by width ascending and height descending.
1 example
Worked Examples
Find LIS length in [10,9,2,5,3,7,101,18]
Mixed-order array; LIS is [2,5,7,101] of length 4.
Patience sorting with binary search on tails array.
Output: 4
Google frequently tests the O(n log n) optimisation; knowing only the O(n²) DP may not pass. Also gateway to Russian Doll Envelopes and box-stacking problems.