iv. LIS, LCS and Edit Distance

Three DPs on sequences with a lot of structure: LIS has an $O(n\log n)$ greedy-DP, LCS reduces to LIS for permutations and runs in $O(nm/64)$ bit-parallel, and edit distance has banded and $O(n+d^2)$ variants. All three can produce the actual answer in linear memory with Hirschberg’s divide and conquer. For LIS of every subarray see Range LIS.

LIS in $O(n\log n)$

tail[k] = smallest possible last element of an increasing subsequence of length $k+1$. It is strictly increasing, so each new element replaces the first tail $\ge x$ (strict LIS) or $>x$ (non-decreasing). A mental model: this is literally the card game patience — deal each card onto the leftmost pile whose top is $\ge$ it; the number of piles is the LIS length, which is why the greedy replacement never loses an achievable length.

Want	Search
strictly increasing	lower_bound
non-decreasing	upper_bound
strictly decreasing	reverse the array (or negate values), then strictly increasing
non-increasing	reverse, then non-decreasing

tail is not an LIS

tail holds the best last-value per length, not an actual achievable subsequence — the values at different indices were never simultaneously the tail at the same time. Reconstructing a real LIS needs the separate predecessor/length bookkeeping the code above already does (par, replayed from tailIdx.back()).

vector<int> lis(const vector<int>& a) {                  // returns indices of one strictly increasing LIS
    vector<int> tailVal, tailIdx, par(sz(a), -1);
    for (int i = 0; i < sz(a); i++) {
        int k = lower_bound(all(tailVal), a[i]) - tailVal.begin();   // upper_bound: non-decreasing
        if (k) par[i] = tailIdx[k - 1];
        if (k == sz(tailVal)) tailVal.push_back(a[i]), tailIdx.push_back(i);
        else tailVal[k] = a[i], tailIdx[k] = i;
    }
    vector<int> res;
    for (int i = sz(tailIdx) ? tailIdx.back() : -1; i != -1; i = par[i]) res.push_back(i);
    reverse(all(res)); return res;
}

Proof: tail stays sorted and its length is the LIS

Invariant after processing a prefix: ${\text{tail}}_k$ is the minimum last element over all increasing subsequences of length $k+1$ in the prefix. Monotonicity: from an increasing subsequence of length $k+2$ ending in $t$, dropping its last element gives one of length $k+1$ ending in something $<t$, so ${\text{tail}}_k<{\text{tail}}_{k+1}$. When $x$ arrives, an increasing subsequence ending at $x$ has length $k+1$ iff the best one of length $k$ ends below $x$, i.e. ${\text{tail}}_{k-1}<x$; the largest such $k$ is the lower-bound position. Extending makes $x$ a candidate for ${\text{tail}}_k$ and it is smaller than the old value (which was $\ge x$), while no other ${\text{tail}}_j$ can improve, because subsequences ending at $x$ of length $j+1\le k$ have last element $x>{\text{tail}}_j$ for $j<k$. The number of tails is therefore the length of the longest one.

Variant	How
number of LIS	Fenwick over values storing (best length, count), merged by max then sum
weighted LIS (max sum increasing)	Fenwick over values storing max
LIS with $a_j<a_i\le a_j+d$	segment tree max over a value window
longest bitonic	LIS ending at $i$ from the left plus from the right
2D chains (envelopes)	sort by $x$ ascending, ties by $y$ descending, then strict LIS on $y$
3D chains	CDQ (CDQ), $O(n{\log }^{2}n)$
LCS of two permutations	map $b$ to positions in $a$, then LIS
min deletions to sort	$n-\text{LIS}$
min number of increasing sequences covering	longest non-increasing subsequence
LIS of all cyclic shifts / all subarrays	seaweed / unit-Monge (Range LIS)

// number of strictly increasing subsequences of maximum length (values compressed to [0, V))
struct Info { int len = 0; mint cnt = 0; };
Info comb(Info a, Info b) { if (a.len != b.len) return a.len > b.len ? a : b; return {a.len, a.cnt + b.cnt}; }
// for each i in order: Info best = prefixQuery(a[i]) (values < a[i]); if (!best.len) best.cnt = 1;
//                      update(a[i], {best.len + 1, best.cnt}); the answer is the query over all values

Proof: covering by monotone sequences (Dilworth/Mirsky for sequences) and Erdős–Szekeres

Cover: the minimum number of non-increasing subsequences covering the sequence equals the LIS length $L$. At least $L$ are needed because two elements of an increasing subsequence can’t share a non-increasing one. Conversely, label each element by the length of the longest increasing subsequence ending at it; elements with equal labels form a non-increasing sequence (if $i<j$ had equal labels and $a_i<a_j$, the label of $j$ would be larger). That’s $L$ classes.
Erdős–Szekeres: any sequence of $rs+1$ distinct numbers has an increasing subsequence of length $r+1$ or a decreasing one of length $s+1$: if every increasing subsequence has length $\le r$, the labels take $\le r$ values, so some label class has $\ge s+1$ elements, and it is decreasing.

LCS

$d{p}_{i,j}=d{p}_{i-1,j-1}+1$ if $a_i=b_j$, else $\max (d{p}_{i-1,j},d{p}_{i,j-1})$. $O(nm)$; reconstruct by walking back.

Counting the number of maximum-length LCSs (not distinct LCS strings, the simpler “how many ways” question): carry a count alongside the length, but guard against double-counting when $a_i\ne b_j$ and $d{p}_{i-1,j}$, $d{p}_{i,j-1}$ tie — both branches may share alignments already counted in $d{p}_{i-1,j-1}$, so subtract cnt[i-1][j-1] by inclusion–exclusion in that case.

Bit-parallel LCS ($O(nm/64)$, about 0.2 s for $n=m=10^5$): the row differences $d{p}_{i,j+1}-d{p}_{i,j}$ are 0/1, so the row is a bit vector, and one row update is a few word operations with a carry (Hyyrö / Crochemore et al.).

struct BitLCS {                                          // b fixed; stream a; LCS(a, b[0, j)) queries
    int m, W; map<int, vector<ull>> mask; vector<ull> v; // v bit j = 0 iff the row increases at j
    BitLCS(const vector<int>& b) : m(sz(b)), W((sz(b) + 63) / 64), v(W, ~0ULL) {
        for (int j = 0; j < m; j++) { auto& mk = mask[b[j]]; if (mk.empty()) mk.assign(W, 0); mk[j >> 6] |= 1ULL << (j & 63); }
    }
    void push(int c) {
        auto it = mask.find(c); if (it == mask.end()) return;
        ull carry = 0;
        for (int w = 0; w < W; w++) {                   // v = (v + (v & M)) | (v & ~M)
            ull x = v[w], y = x & it->second[w], s = x + y, over = s < x;
            s += carry; carry = over | (s < carry);
            v[w] = s | (x & ~it->second[w]);
        }
    }
    int prefix(int j) const {
        int r = 0;
        for (int w = 0; w < j >> 6; w++) r += 64 - __builtin_popcountll(v[w]);
        if (j & 63) r += (j & 63) - __builtin_popcountll(v[j >> 6] & ((1ULL << (j & 63)) - 1));
        return r;
    }
};

Proof sketch: the bit-parallel row update

Let ${\Delta }_j=d{p}_{i,j+1}-d{p}_{i,j}\in \{0,1\}$ and store $v_j=1-{\Delta }_j$. Processing a new character $c$ of $a$, a match at column $j$ ($b_j=c$) can raise the row from column $j$ on, but only up to the next position where the old row already increased. In bit terms, each run of 1s in $v$ (columns without an increase) that contains a match has its lowest matching 1 turned into a 0 (new increase), and the old increase at the run’s end is “absorbed” (turned into a 1). Adding $v\&M$ to $v$ does exactly this: the carry starting at the lowest matched 1 of a run ripples through the run and stops at the 0 that ends it, setting it to 1. Or-ing $v\&\neg M$ restores the unmatched 1s cleared by the carry. The number of increases (zeros) up to $j$ is the LCS with $b[0,j)$.

Other LCS facts:

• Hunt–Szymanski: $O((r+n)\log n)$ where $r$ = number of matching pairs, via LIS over match lists processed right-to-left within a row.
• LCS of $k$ strings is $O(n^k)$ (NP-hard for unbounded $k$); no $O(n^{2-\epsilon })$ for two strings under SETH.
• Longest common substring is a different problem: suffix automaton or suffix array (Suffix Array).
• Longest palindromic subsequence = LCS$(s,\text{rev}(s))$, or interval DP.
• Shortest common supersequence = $n+m-\text{LCS}$.
• Longest common increasing subsequence: for each $i$, sweep $j$ keeping the best $d{p}_{\cdot ,j}$ with $b_j<a_i$: $O(nm)$.
• Count distinct LCS strings: next-occurrence DP from each $(i,j)$ over the alphabet, $O(nm\sigma )$.

Edit distance

$d{p}_{i,j}=\min (d{p}_{i-1,j}+1,d{p}_{i,j-1}+1,d{p}_{i-1,j-1}+[a_i\ne b_j])$ — this is the Levenshtein distance. Applications: spell checking, DNA alignment, diff/version control, OCR post-correction, fuzzy search, plagiarism detection, speech-recognition scoring.

Variant	Change
insert/delete only (LCS distance)	$n+m-2\text{LCS}$
Hamming (replace only)	requires $n=m$, no insert/delete branches
weighted operations	replace the 1s by costs
alphabet-dependent costs	cost[a[i]][b[j]] instead of a flat $[a_i\ne b_j]$
Damerau (adjacent transpositions)	extra branch $d{p}_{i-2,j-2}+1$ if $a_{i-1}{a}_i=b_j{b}_{j-1}$
affine gaps (Gotoh)	three layers: match, gap in $a$, gap in $b$
local alignment (Smith–Waterman)	clamp at 0, take the global max
pattern occurrences with $\le k$ errors	free start in the text: $d{p}_{0,j}=0$
answer $\le k$ known	band $|i-j|\le k$: $O(nk)$
distance $d$ small, long strings	diagonal furthest-reaching (Ukkonen/Myers $O(nd)$; with $O(1)$ LCP queries, Landau–Vishkin $O(n+d^2)$)
need the alignment in linear memory	Hirschberg

Proof: banding and furthest-reaching diagonals

Every step that changes $i-j$ is an insertion or deletion and costs 1, so an alignment of cost $\le k$ never leaves the band $|i-j|\le k$; cells outside can be treated as $\infty$. For the diagonal method: on diagonal $\delta =j-i$, the cells with value $\le e$ form a prefix (values are nondecreasing along a diagonal: $d{p}_{i,j}-d{p}_{i-1,j-1}\in \{0,1\}$, which follows by induction from the recurrence). So it suffices to store, for each $e$ and $\delta$, the furthest row reached with cost $e$, extend it greedily by matching characters (a slide, free), and derive cost $e+1$ from the three neighbouring diagonals. Each $e$ touches $O(e)$ diagonals, and the slides cost $O(n)$ per diagonal naively ($O(nd)$) or $O(1)$ with an LCP structure ($O(n+d^2)$).

Hirschberg: the alignment in $O(n+m)$ memory

The same divide-at-the-midpoint skeleton, reused for speed rather than memory, is exactly Knuth’s optimization and D&C DP optimization — worth noticing once you’ve internalised this version.

Split $a$ at $i=n/2$, compute the last row of the forward DP for $a[0,i)$ against all prefixes of $b$ and of the backward DP for $a[i,n)$ against all suffixes, pick the column $k$ maximising the sum, and recurse on both halves.

vector<int> lcsRow(const string& a, const string& b) {
    vector<int> p(sz(b) + 1), c(sz(b) + 1);
    for (char x : a) { for (int j = 1; j <= sz(b); j++) c[j] = x == b[j - 1] ? p[j - 1] + 1 : max(p[j], c[j - 1]); swap(p, c); }
    return p;
}
string hirschberg(const string& a, const string& b) {
    if (a.empty() || b.empty()) return "";
    if (sz(a) == 1) return b.find(a[0]) != string::npos ? a : "";
    int i = sz(a) / 2;
    string ra(a.rbegin(), a.rend() - i), rb(b.rbegin(), b.rend());
    auto F = lcsRow(a.substr(0, i), b), G = lcsRow(ra, rb);
    int k = 0;
    for (int j = 0; j <= sz(b); j++) if (F[j] + G[sz(b) - j] > F[k] + G[sz(b) - k]) k = j;
    return hirschberg(a.substr(0, i), b.substr(0, k)) + hirschberg(a.substr(i), b.substr(k));
}

Proof: correctness and $O(nm)$ time

Any alignment path through the DP grid crosses row $i$ at some column $k$, and splits into an alignment of $a[0,i)$ with $b[0,k)$ and one of $a[i,n)$ with $b[k,m)$; conversely any such pair concatenates. So the optimum is ${\max }_k{F}_k+G_{m-k}$ and any maximiser is a valid split. Time: the top level costs $c\cdot nm$; the two subproblems have sizes $(n/2)k$ and $(n/2)(m-k)$, totalling $nm/2$; each level halves the total, so the overall time is $\le 2c\cdot nm$. Memory is $O(m)$ for the rows plus the recursion.