Find the longest increasing subsequence.

Find the longest increasing subsequence.

Approach: Use dynamic programming with O(n²) or patience sorting O(n log n).

O(n log n) using patience sorting: Maintain array tails where tails[i] = smallest ending value of increasing subsequence of length i+1. For each x, find first tails[i] >= x using binary search, replace it with x. Length = size of tails.

Follow-up: Return the actual subsequence.

Key concepts: dynamic programming, binary search, optimal substructure.