Advanced · Module 18 · Lesson 7
LIS family
Sequence DP and patience-sorting optimization.
Lesson 111 of 123
1d streakLongest Increasing Subsequence: O(N²) DP to O(N log N) Patience Sorting
The Longest Increasing Subsequence (LIS) problem finds the longest strictly increasing subsequence of an array. The classic dynamic programming recurrence dp[i] = 1 + max(dp[j]) for all j < i with nums[j] < nums[i] runs in O(N²) time. By reformulating LIS using Patience Sorting, we maintain an array of the smallest tail elements of increasing subsequences of various lengths. Because this tails array is strictly sorted, each incoming element can be placed via binary search in O(log N) time, achieving O(N log N) total runtime.
Architectural Boundary · Do Not Confuse
Classic DP: O(N²) Time, O(N) Space
Patience Sort: O(N log N) Time, O(N) Space
Classic DP scans all previous elements j < i for each position. Patience sorting uses binary search on a monotonic tails array to locate the smallest tail greater than or equal to nums[i].
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int low = 0, high = size;
// Binary search for insertion point
while (low < high) {
int mid = low + (high - low) / 2;
if (tails[mid] < x) {
low = mid + 1;
} else {
high = mid;
}
}
tails[low] = x;
if (low == size) size++;
}
return size;
}Active Recall Checkpoint
Does the tails array in Patience Sorting contain the actual elements of the Longest Increasing Subsequence at the end?
Show answer & explanation
No. The tails array contains the minimum possible ending values for subsequences of length 1, 2, ..., size. While its length equals the LIS length, the elements in tails may come from conflicting indices and do not form a valid subsequence.
Use it when
Use Patience Sorting O(N log N) for LIS length queries, Russian Doll Envelopes (2D sorting + LIS), and building minimum piles in card games.
Reconsider when
Use O(N²) classic DP when you must reconstruct the exact sequence path with parent pointers or when additional non-monotonic constraints exist.
Cost Model
Complexity & Trade-offs
When to use it
- Optimization, counting, and feasibility with overlapping subproblems.
- Sequence, grid, interval, tree, subset, and digit constraints.
- Replacing exponential recursion with reusable state.
Common mistakes
- Defining a state that lacks information needed by the transition.
- Iterating in an order that reads unresolved or same-round values.
- Optimizing space before proving dependencies.
Practice prompts
- Reproduce the worked LIS family example without looking at the trace.
- Change one input condition and explain whether the LIS family invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check