The Longest Increasing Subsequence (LIS) problem finds the length of the longest subsequence where each element is strictly greater than the previous. The O(n²) DP solution fills dp[i] = length of LIS ending at index i. The O(n log n) patience sorting approach uses binary search and a patience piles array.
int lis(vector<int>& arr) {
vector<int> piles;
for (int x : arr) {
auto it = lower_bound(piles.begin(), piles.end(), x);
if (it == piles.end()) piles.push_back(x);
else *it = x;
}
return piles.size();
}dp[i] = length of LIS ending at index i. For each i, look at all j<i where arr[j]<arr[i]: dp[i]=max(dp[j]+1). Answer is max(dp). Simple but O(n²).
Maintain an array piles where piles[k] = smallest tail of all increasing subsequences of length k+1. For each element, binary search for its position in piles. Length of piles = LIS length.
Piles stay sorted because each new element is placed at the leftmost pile whose top is >= it. The number of piles equals the LIS length by a beautiful combinatorial argument (Dilworth's theorem).
Quiz coming soon for this algorithm.