Longest Increasing Subsequence — Solution & Editorial

Back to the Problem

Patience sorting: keep tails[k] = smallest possible tail of an increasing subsequence of length k+1; each element replaces its lower_bound. The array length is the answer. O(N²) DP times out at 10⁵.

Complexity: O(N log N)

Watch out: Strictly increasing: use lower_bound, not upper_bound (that would allow equal elements).