Longest Increasing Subsequence

The O(n log n) patience sorting insight: tails[i] is the minimum possible last element of any IS of length i+1. Binary search finds where to extend or replace. The length of tails at the end is the LIS length. The tails array itself is always sorted (provable), enabling binary search. The actual subsequence requires backtracking with a separate array.