1. One-Liner
LIS finds the maximum length of a strictly increasing subsequence—classic O(n²) DP or O(n log n) with tails + binary search.
2. The Problem It Solves
From an array, pick indices i1 < i2 < … with a[i1] < a[i2] < … of maximum length—used in analytics, scheduling, and as a building block for harder DP.
3. The Core Idea
DP view: dp[i] = LIS ending at i. Efficient view: keep smallest tail for each length; replace with binary search—Patience Sorting trick.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Naive DP | For each i, scan j<i with a[j]<a[i] |
| 2. Patience | tails sorted; for x, lower_bound replace |
| 3. Answer | tails size |
5. Dry Run Example
[10,9,2,5,3,7,101,18] → LIS length 4 (e.g. 2,5,7,101).
6. Key Properties
| Property | Value |
|---|---|
| Best time | O(n log n) |
| Reconstruction | Parent pointers optional |
7. Where It Is Used
| Domain | Use |
|---|---|
| Data | Trend extraction |
| Algorithms | Dilworth, box stacking variants |
8. Interview Tips
Derive tails invariant, prove binary search placement, mention non-decreasing variant tweak (<=).
9. Comparison with Other Algorithms
| Approach | Time |
|---|---|
| DP | O(n²) |
| Patience + BS | O(n log n) |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n log n) optimal |
| Space | O(n) |
Implementation Example (PYTHON)
import bisect
def lis_length(nums: list[int]) -> int:
tails: list[int] = []
for x in nums:
i = bisect.bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)