Longest Increasing Subsequence: From O(N^2) Dynamic Programming to O(N log N) Patience Sorting

The Longest Increasing Subsequence (LIS) problem is a classic milestone in algorithm design. While the naive Dynamic Programming approach requires quadratic time, modeling the state transitions as a card game (Patience Sorting) yields an optimal $O(N log N)$ algorithm.

1. The O(N²) Dynamic Programming Baseline

Let dp[i] denote the length of the longest increasing subsequence ending at index i:

dp[i] = 1 + max({ dp[j] for j in 0..i-1 where nums[j] < nums[i] })

2. Optimal O(N log N) Patience Sorting

We maintain an array tails, where tails[len] stores the smallest tail element of all increasing subsequences of length len + 1 discovered so far. Because tails is strictly monotonically increasing, we can use binary search (std::lower_bound in C++) to locate the insertion position in $O(log N)$ time.

// C++20 O(N log N) LIS Implementation
int lengthOfLIS(const vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    return tails.size();
}