ix. Young Tableaux and RSK

The Robinson–Schensted–Knuth (RSK) correspondence maps a sequence to a pair of tableaux $(P,Q)$ of the same shape: $P$ (insertion tableau) has weakly increasing rows, $Q$ (recording tableau) stores when each cell appeared. The shape answers subsequence questions: its first row is the LIS, its number of rows is the longest strictly decreasing subsequence, and by Greene’s theorem the first $k$ rows together give the largest union of $k$ disjoint increasing subsequences.

Quantity	From the shape $\lambda =({\lambda }_1\ge {\lambda }_2\ge \dots )$
longest increasing subsequence	${\lambda }_1$
longest decreasing subsequence (distinct values)	number of rows
max total size of $k$ disjoint increasing subsequences	${\lambda }_1+\cdots +{\lambda }_k$ (Greene)
max total size of $k$ disjoint decreasing subsequences	sum of the first $k$ column lengths
number of permutations with shape $\lambda$	$f_{\lambda }^2$, where $f_{\lambda }$ = number of standard tableaux (hook length formula)

auto [P, Q] = rsk(a);                    // a: any values; rows of P weakly increasing
vector<int> shape = rskShape(a);         // row lengths; shape[0] = LIS length
vector<vector<int>> rows = fastRsk(a);   // insertion tableau P in O(n sqrt n log n) (distinct values)

Row insertion: insert $x$ into row 0; if some element is greater than $x$, the smallest such element is bumped to the next row (use $\ge$ for strictly increasing rows); otherwise $x$ is appended. $Q$ records the step at each new cell. Complexity: rsk is $O(n\cdot \text{rows}\cdot \log n)$, which is $O(n\sqrt{n}\log n)$ for random permutations but $O(n^2\log n)$ in the worst case (a decreasing sequence). fastRsk computes the first $\lceil \sqrt{n}\rceil$ rows directly and the rest from the first rows of the reversed sequence (whose tableau is the transpose for distinct values), for $O(n\sqrt{n}\log n)$ always (Benq / msg555).

template <class T>
pair<vector<vector<T>>, vector<vector<int>>> rsk(const vector<T>& a) {
    vector<vector<T>> P;
    vector<vector<int>> Q;
    for (int step = 0; step < (int)a.size(); step++) {
        T x = a[step];
        for (int r = 0;; r++) {
            if (r == (int)P.size()) {
                P.push_back({x});
                Q.push_back({step});
                break;
            }
            auto it = upper_bound(P[r].begin(), P[r].end(), x);
            if (it == P[r].end()) {
                P[r].push_back(x);
                Q[r].push_back(step);
                break;
            }
            swap(x, *it);
        }
    }
    return {P, Q};
}
 
template <class T>
vector<int> rskShape(const vector<T>& a) {
    auto P = rsk(a).first;
    vector<int> shape;
    for (auto& row : P) shape.push_back(row.size());
    return shape;
}
 
vector<vector<int>> boundedRsk(const vector<int>& a, int k) {   // first k rows of the insertion tableau
    vector<vector<int>> h(k);
    for (int x : a) {
        for (int j = 0; j < k; j++) {
            int p = lower_bound(h[j].begin(), h[j].end(), x) - h[j].begin();
            if (p == (int)h[j].size()) {
                h[j].push_back(x);
                break;
            }
            swap(x, h[j][p]);
        }
    }
    return h;
}
 
vector<vector<int>> fastRsk(vector<int> a) {   // distinct values
    if (a.empty()) return {};
    int rt = (int)ceil(sqrt((double)a.size()));
    auto ha = boundedRsk(a, rt);
    reverse(a.begin(), a.end());
    auto hb = boundedRsk(a, rt);   // rows of the reversed sequence = columns of the original tableau shape
    ha.resize(hb[0].size());
    for (int i = rt; i < (int)hb[0].size(); i++) {
        for (int j = 0; i < (int)hb[j].size(); j++) ha[i].push_back(hb[j][i]);
    }
    while (!ha.empty() && ha.back().empty()) ha.pop_back();
    return ha;
}

Proof: LIS = first row, and the number of rows = longest decreasing subsequence

First row. The first row evolves exactly like patience sorting: each element replaces the smallest larger element of row 0 or extends it, so position $j$ of row 0 holds the smallest possible last element of an increasing subsequence of length $j+1$ seen so far, and the row length equals the LIS. Rows. For distinct values, the tableau of the reversed sequence is the transpose of $P$ (Schensted’s theorem); the first row of the transpose is the first column of $P$, and an increasing subsequence of the reversed sequence is a decreasing subsequence of the original, so the number of rows is the longest decreasing subsequence. This transpose property is also what makes fastRsk correct: rows beyond $\sqrt{n}$ have length below $\sqrt{n}$ (the shape has $n$ cells and its rows are non-increasing), so they lie inside the first $\sqrt{n}$ rows of the transposed tableau.

Proof sketch: Greene's theorem

Greene’s theorem states that ${\lambda }_1+\cdots +{\lambda }_k$ equals the maximum size of a union of $k$ increasing subsequences. The standard proof shows that this maximum is invariant under Knuth relations (swaps of adjacent elements $yxz\leftrightarrow yzx$ and $xzy\leftrightarrow zxy$ for $x<y<z$), which do not change the insertion tableau; every sequence is Knuth-equivalent to the reading word of its tableau $P$ (rows read bottom to top), and for a reading word the maximum is attained by its first $k$ rows. The statement was verified by brute force over all ways to pick two disjoint increasing subsequences for permutations of length $\le 8$.

Proof: RSK is a bijection

Insertion is reversible given the position of the new cell: remove the entry of $P$ at the cell where $Q$ holds the largest step, and reverse-bump upward (in each row above, replace the largest element smaller than the carried value). This recovers the last inserted element and the previous pair of tableaux, so $(P,Q)$ determines the sequence. Conversely every pair of standard tableaux of the same shape arises, since reverse insertion can always be run. Hence permutations of $n$ correspond to pairs of standard tableaux of equal shape, and $n!={\sum }_{\lambda }{f}_{\lambda }^2$.

Related: Sequence DP (LIS), Counting Fundamentals.