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

1. The Classical O(N^2) Dynamic Programming Formulation

Given an integer array nums of size N, the objective is to determine the length of the longest strictly increasing subsequence. We define dp[i] as the length of the longest increasing subsequence that terminates strictly at index i:

Every element can individually form a subsequence of length 1, initializing dp[i] = 1. The nested loops scan all predecessors:

int maxLen = 0;
vector<int> dp(N, 1);
for (int i = 0; i < N; ++i) {
    for (int j = 0; j < i; ++j) {
        if (nums[j] < nums[i]) {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    maxLen = max(maxLen, dp[i]);
}

This algorithm performs N(N - 1) / 2 comparisons. When N = 100,000, quadratic scaling demands 5 billion operations, breaching typical competitive programming and production latency limits.

2. Patience Sorting: Card Game Physics & Monotonic Invariants

To overcome quadratic complexity, we analyze the card game Patience. As cards are dealt one by one from the deck, each card x is placed according to two rules:

1. A card can only be placed on a pile if its value is less than or equal to the current top card of that pile.
2. Greedy Rule: Always place the card on the leftmost valid pile. If no existing pile can accept the card, start a brand new pile to the right.

The Fundamental Invariant: The top elements of all piles are guaranteed to remain strictly sorted in ascending order from left to right at all times.

Consequently, determining which pile accepts a new number does not require linear scanning: we can execute binary search (std::lower_bound) over the pile tops in O(log P) time, where P ≤ N. The total number of piles formed at the conclusion of the game equals the exact length of the Longest Increasing Subsequence.

3. O(N log N) Implementation & State Transitions

Let array tails[k] represent the smallest tail element of all increasing subsequences of length k + 1 discovered so far. By maintaining tails, each incoming element either updates an existing pile top or extends the array:

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); // Create new pile on right
        } else {
            *it = x;            // Greedily minimize tail of current length
        }
    }
    return tails.size();
}

4. Full Subsequence Reconstruction: Parent Index Pointers

A common pitfall is assuming that the tails vector contains the actual LIS. Because earlier elements are overwritten by smaller subsequent numbers, tails only tracks minimal tail bounds, not chronological sequence validity.

To extract the actual elements forming the subsequence, we store the original array indices inside tails and maintain a parent[i] predecessor link:

vector<int> reconstructLIS(const vector<int>& nums) {
    int n = nums.size();
    vector<int> tailsIndices;
    vector<int> parent(n, -1);

    for (int i = 0; i < n; ++i) {
        int left = 0, right = tailsIndices.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[tailsIndices[mid]] < nums[i]) left = mid + 1;
            else right = mid;
        }
        if (left > 0) parent[i] = tailsIndices[left - 1];
        if (left == tailsIndices.size()) tailsIndices.push_back(i);
        else tailsIndices[left] = i;
    }

    vector<int> lis;
    for (int curr = tailsIndices.back(); curr != -1; curr = parent[curr]) {
        lis.push_back(nums[curr]);
    }
    reverse(lis.begin(), lis.end());
    return lis;
}

5. Multi-Dimensional Extensions: Russian Doll Envelopes

In two dimensions, we are given envelopes [width, height] where envelope A fits into envelope B if and only if A.w < B.w and A.h < B.h. A naive search yields O(N^2).

We can reduce this 2D problem to 1D LIS through asymmetric sorting:

Because height is sorted descending when widths match, two envelopes with identical widths cannot form an increasing subsequence in height. Applying 1D LIS on the height sequence directly solves the 2D problem in O(N log N) time.

6. Range Query Accelerations: Fenwick Trees & Counting Distinct LIS

While patience sorting with binary search is the gold standard for computing the maximum length of an increasing subsequence, it struggles when requirements demand counting the total number of distinct LIS sequences or handling dynamic online point updates.

By discretizing array values through coordinate compression into ranks [1, U] where U ≤ N, we can maintain a Fenwick Tree (Binary Indexed Tree) or Segment Tree over the value domain:

• Tree State: Each tree node stores a pair {maxLength, count} representing the maximum subsequence length ending with values in that range and its multiplicity modulo 10^9 + 7.
• Query & Update: For each element x, query the prefix range [1, rank(x) - 1] in O(log N) time to obtain {L, C}. Update position rank(x) with {L + 1, C} in O(log N) time.
• Combinatorial Counting: Unlike patience sorting which overwrites duplicate paths, the Fenwick tree naturally aggregates multiple combinatorial paths of equal maximal length in O(N log N) time.

7. Complexity Comparison: LIS Algorithmic Matrix