CONCEPT · Expert
Longest increasing subsequence
also LIS · patience sorting · tails array
Longest strictly increasing subsequence (order preserved, not necessarily contiguous). O(n²) DP ends at each index; patience/tails with binary search is O(n log n) for the length.
Intuition
At i you only care about the best smaller tail to the left. Tails remembers, for each length, the smallest ending value so later numbers can still extend it.
When to reach for it
- Length of a strictly increasing subsequence
- n ≤ 2e3 with a double loop; n ≤ 1e5 with tails + lower bound
- As a reduction: longest non-decreasing, or LIS on a pair of sequences (LCS of the array and its sorted unique version)
Usual pits
- Confusing subsequence with subarray (contiguous)
- Using ≤ when the statement is strict (equals must not extend)
- Treating the tails array as an actual LIS — replacements scramble it; it only stores length
- O(n²) at n = 1e5