Longest Increasing Subsequence
Problem
nums, return the length of the longest
subsequence whose values are strictly increasing. A subsequence keeps the original
order but may skip elements (it need not be contiguous).[10,9,2,5,3,7,101,18]Output4 ([2,3,7,18])[0,1,0,3,2,3]Output4[7,7,7,7]Output11 ≤ n ≤ 2500 · -104 ≤ nums[i] ≤ 104 · Follow-up: O(n log n) time.
Try it yourself
class Solution {
public int lengthOfLIS(int[] nums) {
}
}
k keep only the smallest possible tail of an
increasing subsequence of length k. These tails are sorted, so each new number
either extends the longest one or replaces the first tail ≥ it (binary search).Instinct Longest chain where each pick must beat the last (bigger, later, fits inside) - O(n²) best-ending-here DP, or O(n log n) tails plus binary search.
Memory hack Patience solitaire - drop each card on the leftmost pile whose top is not smaller; the number of piles is the LIS length.
Open the Longest Increasing Subsequence guide →Approaches
Brute ForceRecursion (Take / Skip)
O(2n)Space O(n)Walk the array remembering the index prev of the last taken
element. At index i either skip it, or take it if it is larger than
nums[prev]. This explores every subsequence.
public int lengthOfLIS(int[] nums) { return lis(nums, 0, -1); } private int lis(int[] nums, int i, int prev) { if (i == nums.length) return 0; int skip = lis(nums, i + 1, prev); int take = 0; if (prev == -1 || nums[i] > nums[prev]) take = 1 + lis(nums, i + 1, i); return Math.max(skip, take); }
Simple and correct, but exponential — hopeless beyond n ≈ 25.
BetterDP — LIS Ending at Each Index
O(n2)Space O(n)dp[i] = length of the longest increasing subsequence that
ends at nums[i]. It extends the best earlier
dp[j] with nums[j] < nums[i], or starts fresh at 1.
The answer is max(dp), not dp[n-1].
public int lengthOfLIS(int[] nums) { int[] dp = new int[nums.length]; Arrays.fill(dp, 1); // each element alone int best = 1; for (int i = 0; i < nums.length; i++) { for (int j = 0; j < i; j++) if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1); best = Math.max(best, dp[i]); } return best; }
Clean quadratic DP; fine for n = 2500 but misses the O(n log n) follow-up.
OptimalPatience Sorting (Tails + Binary Search)
O(n log n)Space O(n)tails[k] = smallest tail of any increasing subsequence of
length k+1; it is strictly increasing. For each num,
binary-search the first tail ≥ num: overwrite it (a smaller tail is
never worse), or append if none exists. size is the LIS length;
tails itself is not necessarily a valid subsequence.
public int lengthOfLIS(int[] nums) { int[] tails = new int[nums.length]; int size = 0; for (int num : nums) { int lo = 0, hi = size; // first index with tails[i] >= num while (lo < hi) { int mid = lo + (hi - lo) / 2; if (tails[mid] < num) lo = mid + 1; else hi = mid; } tails[lo] = num; if (lo == size) size++; // extended the longest run } return size; }
Dry runtails for [10,9,2,5,3,7,101,18]
- 10,9,22s···each replaces tails[0]
- 525s··5 > all → append
- 323s··replace 5 (smaller tail)
- 7237s·append
- 101237101sappend
- 1823718sreplace 101 → size 4 ✔
Meets the follow-up; the go-to LIS technique.
num instead (upper bound).At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Recursion (Take / Skip) | O(2n) | O(n) |
| Better | DP — LIS Ending at Each Index | O(n2) | O(n) |
| Optimal | Patience Sorting (Tails + Binary Search) | O(n log n) | O(n) |
- Returning
dp[n-1]instead ofmax(dp)— the LIS may end earlier. - Using
<=in the binary search — allows equal values (not strictly increasing). - Claiming
tailsis the actual subsequence — only its length is meaningful.
- Define the DP state precisely: “LIS that ends at i”.
- Justify the greedy: a smaller tail leaves more room for future elements.
- To rebuild the sequence, store tail indices plus a parent array.