Longest Increasing Subsequence

Find the longest subsequence (not necessarily contiguous) that is strictly increasing.

$O(n^2)$ DP

$dp[i]=1+\max \{dp[j]:j<i,a_j<a_i\}.$

vector<int> dp(n, 1);
for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
int ans = *max_element(dp.begin(), dp.end());

Simple, easy to modify, and enough for $n\le 5000$.

$O(n\log n)$ — the patience trick

Keep tail[k] = the smallest possible tail of an increasing subsequence of length $k+1$. This array is always sorted, so each element is placed with a binary search.

int lis(vector<int>& a) {
    vector<int> tail;
    for (int x : a) {
        auto it = lower_bound(tail.begin(), tail.end(), x);   // strictly increasing
        if (it == tail.end()) tail.push_back(x);
        else *it = x;
    }
    return tail.size();
}

tail is not an LIS

The array holds the best tails per length, not an actual subsequence. To recover a real LIS, record for each element the length at which it was placed and its predecessor, then walk back.

vector<int> lisReconstruct(vector<int>& a) {
    int n = a.size();
    vector<int> tail, tailIdx, par(n, -1);
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(tail.begin(), tail.end(), a[i]);
        int pos = it - tail.begin();
        if (pos > 0) par[i] = tailIdx[pos - 1];
        if (it == tail.end()) { tail.push_back(a[i]); tailIdx.push_back(i); }
        else { *it = a[i]; tailIdx[pos] = i; }
    }
    vector<int> res;
    for (int i = tailIdx.back(); i != -1; i = par[i]) res.push_back(a[i]);
    reverse(res.begin(), res.end());
    return res;
}

Strict vs non-strict

Want	Use
Strictly increasing	lower_bound
Non-decreasing	upper_bound
Strictly decreasing	reverse the array, or negate values, then strict increasing
Non-increasing	reverse + non-decreasing

Getting this wrong is a one-character bug that produces plausible wrong answers.

Variants

Variant	Approach
Count the number of LIS	keep (length, count) per value in a segment tree over compressed values, or a second DP array
Longest bitonic subsequence	LIS from the left + LIS from the right, combine at each index
LIS with a bounded gap ($a_i-a_j\le d$)	segment-tree max query over a value range
Longest chain of pairs / boxes	sort by one dimension (ties descending), LIS on the other
3D version (boxes in boxes)	sort by one, then a 2D dominance DP with a BIT, $O(n{\log }^{2}n)$
Minimum deletions to sort	$n-\mathrm{LIS}$
Minimum non-increasing subsequences covering the array	$=\mathrm{LIS}$ (Dilworth)
LIS of a permutation, huge $n$	the $O(n\log n)$ method is already optimal
LCS of two permutations	map to indices, then LIS — $O(n\log n)$ instead of $O(n^2)$

That last one is worth remembering: the LCS of two permutations of the same set is exactly an LIS problem, which turns a quadratic algorithm into an $n\log n$ one.

Dilworth’s theorem

The minimum number of non-increasing subsequences needed to cover a sequence equals the length of its longest increasing subsequence.

Equivalently: the minimum number of increasing subsequences covering the array equals the longest non-increasing subsequence. This converts several “partition into monotone pieces” problems into a single LIS computation.

Patience sorting

The $O(n\log n)$ algorithm is literally the card game patience: deal cards into piles, placing each on the leftmost pile whose top is $\ge$ the card. The number of piles is the LIS length. It is a good mental model for why the greedy tail replacement is correct — replacing a tail never shortens any achievable length and can only help future elements.

See also: LCS · Binary Search · Segment Tree