2. What is the repeated work?

The best chain from index `i` onwards with last-taken value `v` is solved again for every path that reached that state. Turn it around: the best chain that **ends at `i`** doesn't depend on how we got there.

3. How do we fill dp?

`dp[i] = 1 + max(dp[j])` for `j < i` with `a[j] < a[i]`. On `[3, 1, 4, 1, 5]`: dp = `[1, 1, 2, 1, 3]` → answer 3 (`1, 4, 5` or `3, 4, 5`). **O(N²)**.

4. Can we avoid checking every j?

For each length, only the **smallest tail** matters: a chain ending in a smaller value can be extended by more numbers. Keep `tails`; it is always sorted. For each `x`, `lower_bound(x)` finds the first tail ≥ x: replace it (a better tail for that length) or append (a longer chain). **O(N log N)**.

5. Is tails the answer chain?

**No** — only its length is. On `[3, 4, 1]` tails ends as `[1, 4]`, but `1, 4` is not a subsequence (1 comes after 4). To rebuild a chain, use the O(N²) table with a `parent[i]` per cell (or store indices in tails).

Sort by the first dimension, then run LIS on the second. Ties need care: for **strictly** bigger in both (envelopes) sort equal widths by height **descending**, so two of the same width can never both be in one increasing run.

DP — Longest Increasing Subsequence Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

Q: 1. What would brute force do?

Try every subsequence: take or skip each element, remembering the last one taken. **O(2^N)**.

Q: 4. Can we avoid checking every j?

For each length, only the **smallest tail** matters: a chain ending in a smaller value can be extended by more numbers. Keep `tails`; it is always sorted. For each `x`, `lower_bound(x)` finds the first tail ≥ x: replace it (a better tail for that length) or append (a longer chain). **O(N log N)**.

Q: 5. Is tails the answer chain?

**No** — only its length is. On `[3, 4, 1]` tails ends as `[1, 4]`, but `1, 4` is not a subsequence (1 comes after 4). To rebuild a chain, use the O(N²) table with a `parent[i]` per cell (or store indices in tails).

Q: 6. What about pairs?

Sort by the first dimension, then run LIS on the second. Ties need care: for **strictly** bigger in both (envelopes) sort equal widths by height **descending**, so two of the same width can never both be in one increasing run.

Q: What is the difference between Subsequence (LIS) and Subarray (increasing run)?

Can you skip elements? Yes → LIS with dp over every earlier `j`. No → one pass that resets on a drop.

Q: What is the difference between lower_bound and upper_bound?

Strictly increasing (no equal neighbours) → `lower_bound`. Non-decreasing (equal values allowed) → `upper_bound`.

Q: What is the difference between tails array and The actual LIS?

`tails.size()` is the length. The values in `tails` can come from different chains; rebuild with parents if the chain is needed.

Q: What is the difference between Russian dolls (strict) and Building bridges (non-strict)?

Strict in both → sort ties descending, `lower_bound`. Equal allowed on the second → sort ties ascending, `upper_bound`.

dp[i] = length of the best increasing chain that ends at i. Faster version: keep the smallest possible tail for each length.

3 sub-patterns · 12 questions

Remember this · DP — Longest Increasing Subsequence

Trigger

Longest chain where each item must be bigger/fit inside the previous one (numbers, pairs, envelopes, words).

Think

Does each element extend the best chain ending at some smaller earlier element?

Key question

Sort first? Then what does "increasing" mean for these items?

What is this pattern?

LIS: pick elements in order (not necessarily next to each other) so each one is bigger than the one before, and make the chain as long as possible.

O(N²): dp[i] = the length of the longest increasing chain that ends at i. It is 1 + max dp[j] over every earlier j with a[j] < a[i] (or 1 if there is none). The answer is the biggest dp[i].
O(N log N): keep tails[k] = the smallest possible last value of an increasing chain of length k + 1. tails is sorted, so each new number finds its place with binary search (lower_bound): it either extends the longest chain or replaces a bigger tail.

The same "ends at i, built from an earlier j" idea works whenever you can say which earlier item may come before this one: divides it, is a word with one letter removed, is smaller in both dimensions. For 2-D items, sort by one dimension first, then run LIS on the other.

Stacking cards in piles (patience sorting): each card goes on the leftmost pile whose top card is not smaller than it, or starts a new pile. The number of piles at the end is the length of the longest increasing subsequence — and the pile tops are exactly the tails array.

See it move

Purple = earlier values smaller than nums[i] (they can come before it), red = not smaller, green = the one chosen.

LIS in O(N²): extend the best earlier chainnums = [3, 1, 4, 1, 5, 9, 2, 6]step 1/10

nums

parent

dp[i] = longest chain ending at i

dp[i] = the length of the longest increasing chain that ends exactly at nums[i]. parent[i] = the index before i in that chain (− = none).

pos = lower_bound(x) in tails. Green = appended (a longer chain), orange = replaced (same length, smaller tail).

LIS in O(N log N): the tails arraynums = [3, 1, 4, 1, 5, 9, 2, 6]step 1/10

nums

tails

tails starts empty

tails[k] = the smallest last value of any increasing chain of length k + 1 seen so far. It stays sorted, so we can binary search it.

How do I recognise it?

"Longest increasing subsequence" — order matters, gaps are allowed.
A chain where each item must fit after the previous one: divisible by it, one letter longer, bigger in both width and height.
Pairs / boxes / envelopes / people that must be sorted before they can be chained.
"How many longest increasing subsequences", "maximum sum increasing subsequence" — the same table with a different value per cell.
"Return the chain itself" → keep a parent index per cell and walk back.

Looks like DP — Longest Increasing Subsequence, but isn't

Longest increasing subarray (contiguous)

→ One pass / sliding window

Contiguous means each element only extends the run right before it. LIS lets you skip elements, so any earlier element can be the one before.

Longest common subsequence of two strings

→ DP — Strings (LCS)

LCS compares two sequences with a 2-D table. LIS has one sequence and a rule about order between its own elements.

Maximum number of non-overlapping intervals

→ Greedy (sort by end time)

It looks like a chain, but picking the interval that ends first is always safe, so no DP is needed.

Merge or count overlapping intervals

→ Intervals pattern

No chain is being built; you just sweep the sorted intervals.

How would I discover it from scratch?

Don't memorise “use dp — longest increasing subsequence”. Ask these questions in order — the pattern falls out.

Try every subsequence: take or skip each element, remembering the last one taken. O(2^N).

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

Classic LIS

4 questions

The plain LIS and its cousins: length, count of longest chains, maximum-sum chain, or just "is there a chain of 3".

Chains and reconstruction

4 questions

Same dp[i] = 1 + max dp[j], with a different "may come before" rule, and often a parent array to return the chain itself.

2D / envelopes

4 questions

Items with two (or three) dimensions. Sort by one dimension so the order is fixed, then LIS on the other.

Don't mix these up

Subsequence (LIS) vs Subarray (increasing run)

Can you skip elements? Yes → LIS with dp over every earlier j. No → one pass that resets on a drop.

lower_bound vs upper_bound

Strictly increasing (no equal neighbours) → lower_bound. Non-decreasing (equal values allowed) → upper_bound.

tails array vs The actual LIS

tails.size() is the length. The values in tails can come from different chains; rebuild with parents if the chain is needed.

Russian dolls (strict) vs Building bridges (non-strict)

Strict in both → sort ties descending, lower_bound. Equal allowed on the second → sort ties ascending, upper_bound.

Code templates (C++)

LIS: O(N²) table and O(N log N) tails

lower_bound = strictly increasing; upper_bound = non-decreasing (equal values may repeat).

lis-template.cpp

// O(N^2): dp[i] = length of the longest increasing chain that ends at i.
int lisQuadratic(const vector<int>& a) {
    int n = a.size(), best = 0;
    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);
        best = max(best, dp[i]);
    }
    return best;
}

// O(N log N): tails[k] = smallest last value of an increasing chain of length k + 1.
// tails is sorted; it gives the LENGTH only, not the chain itself.
int lisFast(const vector<int>& a) {
    vector<int> tails;
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);   // upper_bound for non-decreasing
        if (it == tails.end()) tails.push_back(x);   // longer than every chain so far
        else *it = x;                                // a smaller tail for that length
    }
    return tails.size();
}

Chain with a custom rule + rebuild

Only canFollow(j, i) changes between problems (divides, one letter added, …). parent lets you walk back from the best end.

chain-template.cpp

// Longest chain with a custom "j may come before i" rule, returned as the actual chain.
// Shown for divisibility (Largest Divisible Subset); sort first so the rule only looks back.
vector<int> longestChain(vector<int> a) {
    sort(a.begin(), a.end());
    int n = a.size(), end = 0;
    vector<int> dp(n, 1), parent(n, -1);
    auto canFollow = [&](int j, int i) { return a[i] % a[j] == 0; };
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (canFollow(j, i) && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; parent[i] = j; }
        if (dp[i] > dp[end]) end = i;
    }
    vector<int> chain;
    for (int i = n ? end : -1; i != -1; i = parent[i]) chain.push_back(a[i]);   // walk back
    reverse(chain.begin(), chain.end());
    return chain;
}

2-D: sort, then LIS

The sort order is the whole trick: ascending by width, descending by height for equal widths, then strict LIS on heights.

envelope-template.cpp

// 2-D chain, strictly bigger in both dimensions (Russian Doll Envelopes).
// Sort width ascending, and height DESCENDING for equal widths, then strict LIS on heights:
// two envelopes of the same width can never both be in one increasing run.
int maxNested(vector<vector<int>> env) {
    sort(env.begin(), env.end(), [](const vector<int>& x, const vector<int>& y) {
        return x[0] != y[0] ? x[0] < y[0] : x[1] > y[1];
    });
    vector<int> tails;
    for (auto& e : env) {
        auto it = lower_bound(tails.begin(), tails.end(), e[1]);
        if (it == tails.end()) tails.push_back(e[1]);
        else *it = e[1];
    }
    return tails.size();
}

Start with Classic LIS