Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sorting & Dilworth's Theorem

1. State Inversion: From $O(N^2)$ Prefix DP to $O(N \log N)$ Monotonic Tails

The textbook $O(N^2)$ recurrence defines $dp[i]$ as the length of the Longest Increasing Subsequence ending at $A[i]$: $dp[i] = 1 + \max_{j < i, A[j] < A[i]} dp[j]$. To break the $O(N^2)$ barrier, we apply State-Value Inversion:

Define $\text{tails}[L]$ (0-indexed for length $L + 1$) as the minimum possible ending value among all strictly increasing subsequences of length $L + 1$ seen so far in prefix $A[0..i]$.

2. Patience Sorting & Dilworth's Theorem (Chain / Antichain Duality)

Imagine dealing cards $A[0..n-1]$ into piles from left to right according to Patience Sorting (Aldous & Diaconis, 1999): place card $x$ on the leftmost pile whose top card is $\ge x$ (or start a new pile to the right if all pile tops are $< x$). Each pile is a non-increasing subsequence, and the top cards of the piles from left to right are literally our array $\text{tails}[0..k-1]$!

• Dilworth's Theorem (1950): In any finite partially ordered set, the minimum number of disjoint chains (non-increasing subsequences) needed to partition the sequence equals the maximum size of an antichain (strictly increasing subsequence). Thus:
  • Minimum number of non-increasing subsequences to cover $A$ $=$ Length of Strictly Increasing LIS (lower_bound).
  • Minimum number of strictly decreasing subsequences to cover $A$ $=$ Length of Non-Decreasing LNDS (upper_bound).
• 2D Envelope / Russian Doll Nesting $(w_i, h_i)$: To find the longest chain where both $w_a < w_b$ and $h_a < h_b$, sort pairs by $w_i$ ascending, and on ties by $h_i$ DESCENDING, then run 1D strictly increasing LIS on $h_i$! Sorting ties by $h_i$ descending guarantees we can never pick two envelopes with the same width $w$.

3. Complexity Matrix

4. Reference C++20 Implementation

#include <algorithm>
#include <cstdint>
#include <vector>

// 1. O(N log N) Strictly Increasing Subsequence with Full Sequence Reconstruction
std::vector<int> longest_increasing_subsequence(const std::vector<int>& nums) {
    const int n = static_cast<int>(nums.size());
    if (n == 0) return {};

    std::vector<int> tails;          // tails[len] = smallest ending value of LIS of length len+1
    std::vector<int> tail_idx;       // tail_idx[len] = index in nums that achieved tails[len]
    std::vector<int> parent(n, -1);  // parent[i] = predecessor index in nums for element i

    for (int i = 0; i < n; ++i) {
        auto it = std::lower_bound(tails.begin(), tails.end(), nums[i]);
        int pos = static_cast<int>(it - tails.begin());

        if (it == tails.end()) {
            tails.push_back(nums[i]);
            tail_idx.push_back(i);
        } else {
            *it = nums[i];
            tail_idx[pos] = i;
        }
        if (pos > 0) {
            parent[i] = tail_idx[pos - 1];
        }
    }

    // Reconstruct valid subsequence backward from the index of the longest pile top
    std::vector<int> result(tails.size());
    int curr = tail_idx.back();
    for (int k = static_cast<int>(tails.size()) - 1; k >= 0; --k) {
        result[k] = nums[curr];
        curr = parent[curr];
    }
    return result;
}

// 2. 2D Russian Doll Envelopes: Sort (w ASC, h DESC) + 1D LIS on h
int max_nested_envelopes(std::vector<std::pair<int, int>> envelopes) {
    std::sort(envelopes.begin(), envelopes.end(), [](const auto& a, const auto& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second > b.second; // DESCENDING height on equal width prevents duplicate width picks!
    });

    std::vector<int> tails;
    for (const auto& [w, h] : envelopes) {
        auto it = std::lower_bound(tails.begin(), tails.end(), h);
        if (it == tails.end()) tails.push_back(h);
        else *it = h;
    }
    return static_cast<int>(tails.size());
}