DP IV — Subsequences (LIS / LCS)

Review boundary and corrected contracts

tails[k] is the minimum feasible final value for a length-(k+1) increasing subsequence, not necessarily one common witness subsequence. bisect_left enforces strict increase. LCS with the reversed string gives the palindrome subsequence length; arbitrary reconstructed LCS witnesses need not themselves be palindromes.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own the two parent subsequence problems — LIS and LCS — so completely that the dozen problems built on them become recognition instead of invention.

Series: LeetCode — From Basics to Production-Ready · Session 36 / 65 · Phase 2 · Dynamic programming

Prerequisites

You need L33–L35: what a DP state is, how a recurrence is derived, and the memo→table transition. If "define the state in one English sentence" does not yet feel automatic, re-do L33 first. Everything here is that skill applied to two specific state shapes.

Watch first (skim before the session)

Optional original video routes: LIS recurrence, LCS grid and reconstruction, and binary-search LIS. Before watching, predict the LIS of [5, 6, 1] and the LCS of "abcde" and "ace"; the worked sections below answer both.

Why this session exists

Two problems generate an entire family. Longest Increasing Subsequence (LIS) asks: inside one array, what is the longest chain that keeps going up? Longest Common Subsequence (LCS) asks: across two strings, what is the longest sequence you can read off both, in order, without rearranging?

Once you can write both from memory, a surprising number of "new" problems collapse into one of them plus a twist: Longest Palindromic Subsequence is just LCS of a string with its own reverse. Edit Distance (L40) uses a related prefix grid but different transitions and costs; with substitutions it is not determined by LCS length alone. Russian Doll Envelopes is LIS after a sort. Maximum Length of Pair Chain is LIS in disguise. The leverage here is enormous — two templates unlock a dozen mediums.

Subsequence vs substring

Real: A subsequence is what you get by deleting some letters from a word without reordering the rest — like reading only the capital letters in a ransom note. A substring is a contiguous run. 'ace' is a subsequence of 'abcde' but not a substring. Reviewers love this distinction because candidates conflate the two under pressure.

s = "abcde"
# subsequence: pick indices in increasing order, skip freely
#   a _ c _ e  -> "ace"  (valid subsequence)
# substring: must be contiguous
#   "ace" is NOT a substring of "abcde"

Blank-file warm-up

Five minutes, empty file, no notes. Write both cores from memory:

LIS:  dp[i] = 1 + max(dp[j] for j < i if a[j] < a[i]), else 1
LCS:  dp[i][j] = dp[i-1][j-1] + 1        if a[i-1] == b[j-1]
                 max(dp[i-1][j], dp[i][j-1])   otherwise

If you cannot reproduce these cold, you do not know the session yet. Review, then start.

LIS from first principles

Question: Why does dp[i] = 1 + max over earlier smaller elements give the LIS length?

Premise: Define dp[i] = length of the longest increasing subsequence that ENDS exactly at index i.

Because: Anchoring the subsequence at its last element removes ambiguity: every increasing subsequence ends somewhere, so the global answer is max(dp).

Premise: Any increasing subsequence ending at i has some previous element at index j < i with a[j] < a[i], OR i is the very first element of its chain.

Because: Removing the final element leaves an increasing subsequence ending at j of length at most dp[j]. Conversely, an optimal chain of length dp[j] can be extended by a[i], since its last value is smaller. These upper and lower bounds justify taking the maximum.

Premise: So dp[i] = 1 + max(dp[j]) over all j < i with a[j] < a[i]; if no such j, dp[i] = 1.

Because: We extend the best compatible chain by one (the +1 for element i itself).

Premise: The global answer is max(dp[i]) over all i, not dp[n-1].

Because: The longest chain need not end at the last element.

Conclusion: LIS is take/skip DP where 'compatible' means strictly larger, and the answer is the best chain-ending value anywhere in the array.

def length_of_lis(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n                       # every element is a chain of length 1 by itself
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:      # strictly increasing
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp) if dp else 0        # answer can end anywhere
 
assert length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]) == 4   # [2,3,7,101] or [2,3,7,18]
assert length_of_lis([0, 1, 0, 3, 2, 3]) == 4
assert length_of_lis([7, 7, 7, 7]) == 1

That is O(n²). Reviewers who ask LIS almost always escalate to: can you do better than n²? The answer is O(n log n) with patience sorting, but reaching it requires changing what a table entry represents. Instead of keeping one result per ending index, keep the smallest possible ending value for each chain length. Of two equally long chains, the one with the smaller tail can accept every future value the larger tail can accept, and possibly more, so the larger tail can be forgotten. Those minimum tails are ordered by chain length, which lets binary search find the slot a new value improves. We are compressing the choices for future extension, not constructing one actual subsequence.

from bisect import bisect_left
 
def length_of_lis_fast(nums: list[int]) -> int:
    tails: list[int] = []              # tails[k] = smallest possible tail of an increasing subseq of length k+1
    for x in nums:
        i = bisect_left(tails, x)      # first tail >= x
        if i == len(tails):
            tails.append(x)            # x extends the longest chain
        else:
            tails[i] = x               # x gives a smaller tail for a length-(i+1) chain
    return len(tails)                  # length of tails == LIS length
 
assert length_of_lis_fast([10, 9, 2, 5, 3, 7, 101, 18]) == 4

tails is NOT the LIS itself — it is a bookkeeping array whose length equals the LIS length. Do not present its contents as the answer subsequence; reviewers catch this. If they want the actual subsequence, keep a parent-pointer array alongside the n² DP.

LCS from first principles

Question: Why does the LCS recurrence branch on whether the last characters match?

Premise: Define dp[i][j] = LCS length of a[:i] (first i chars of a) and b[:j] (first j chars of b).

Because: Prefix-by-prefix is the natural decomposition for two-string DP: shrink one prefix at a time.

Premise: If a[i-1] == b[j-1], those two characters can BOTH be the last character of a common subsequence, so dp[i][j] = dp[i-1][j-1] + 1.

Because: Appending the matching character to an optimal solution on the two shorter prefixes achieves dp[i−1][j−1] + 1. For the upper bound, a common subsequence either uses neither final position, or its final matched character can be removed to leave a common subsequence of the shorter prefixes. Thus no solution is longer than that value.

Premise: If they differ, at least one of them is not in the LCS, so dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Because: We try dropping the last char of a, or the last char of b, and keep the better result.

Premise: Base case dp[0][j] = dp[i][0] = 0.

Because: An empty prefix shares nothing with anything.

Conclusion: LCS is a 2D grid DP: match the diagonal +1, else take the better of the two neighbours. This exact shape reappears in Edit Distance, Distinct Subsequences, and Shortest Common Supersequence.

def lcs(a: str, b: str) -> int:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1        # matched last chars
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]
 
assert lcs("abcde", "ace") == 3        # "ace"
assert lcs("abc", "abc") == 3
assert lcs("abc", "def") == 0

The table has O(mn) cells, each filled in O(1), so O(mn) time and space. Space drops to O(n) with two rolling rows — a common follow-up.

Mental model

Name: Two parents, many children

Picture: A family tree with exactly two roots. LIS sits over one array; LCS sits over two strings. Below them hang the children: LPS = LCS(s, reverse(s)); Edit Distance uses a related prefix grid with insert/delete/replace transitions; Russian Doll Envelopes = sort then LIS; Max Length of Pair Chain = LIS on intervals. When a subsequence problem appears, first ask: is this LIS-shaped (one sequence, monotone condition) or LCS-shaped (two sequences, alignment)?

• One sequence + a 'keeps going up/down' condition ⇒ LIS family.

• Two sequences aligned in order ⇒ LCS family.

• A palindrome subsequence-length question ⇒ LCS length with the reverse; palindrome reconstruction needs additional care.

• If the O(n^2) LIS DP is accepted, offer the O(n log n) patience version as the follow-up before they ask.

Trigger: The word 'subsequence' plus either a monotonicity rule (LIS) or a second string (LCS).

Memory hook

"LIS ends here; LCS matches the corner." LIS DP is anchored at the ending index (answer is max(dp), not dp[-1]). LCS DP branches on the corner diagonal cell (dp[i-1][j-1]) when the last characters match. Say the sentence out loud twice; it encodes the one detail people forget about each — where LIS's answer lives, and which neighbour LCS reaches on a match.

Myth: The LIS answer is dp[n-1] (the value at the last index), just like most 1D DP.

Truth: It is max(dp) over the whole array. The longest increasing chain can end at any element, not necessarily the last one.

Why: In [10, 9, 2, 5, 3, 7, 101, 18], an optimal length-4 chain can end at either 101 or 18, so dp[-1] happens to work. On [5, 6, 1], it gives 1 instead of the correct global maximum 2.

Test: Ask yourself: could a shorter suffix drag the answer down if I read dp[-1]? If yes, you must take the max.

What reviewers actually ask

Real problems that live in this family, with what a reviewer is probing.

• LC300 · Longest Increasing Subsequence — Practice selection. They want the O(n²) DP first (proves you can define the state), then push for O(n log n). The probe: can you explain why patience sorting's tails length equals the LIS length? Follow-up: reconstruct the actual subsequence, or count how many distinct LIS there are (LC673).
• LC1143 · Longest Common Subsequence — Practice selection. The canonical 2D-string DP. Probe: the match-vs-mismatch branch and the base row/column. Follow-up: reduce space to O(min(m,n)) with rolling rows, or return the subsequence itself.
• LC516 · Longest Palindromic Subsequence — Practice selection. The "aha" is that it equals LCS(s, reverse(s)). Probe: do you see the reduction, or do you reinvent an interval DP? Both are accepted; the reduction is the elegant answer.
• LC1035 · Uncrossed Lines — Practice selection. Word-dressed LCS on two integer arrays. Probe: can you strip the story and recognise the parent problem?
• LC354 · Russian Doll Envelopes — Practice selection. Sort by width ascending, height descending, then LIS on heights. Probe: why the descending tie-break on height matters (it forbids stacking two envelopes of equal width). This one separates people who memorised LIS from people who understand it.
• LC673 · Number of Longest Increasing Subsequences — Practice selection. LIS with a parallel count array. Probe: careful bookkeeping when dp[j] + 1 == dp[i] (add counts) vs > dp[i] (reset).

The universal escalation ladder here: n² DP → n log n (LIS) or O(min(m,n)) space (LCS) → reconstruct the actual sequence → count how many optimal sequences exist.

A worked reduction: Longest Palindromic Subsequence

Brute force would try every subsequence — exponential. The useful equality is between lengths: LPS-length(s) = LCS-length(s, reverse(s)). Every palindromic subsequence is common to both strings, but a common subsequence need not itself be a palindrome.

For the converse length bound, match a length-k common subsequence to increasing positions i_1…i_k in s and decreasing positions j_1…j_k in s (the second embedding read through the reverse). The pairs i_t < j_t form a prefix of length a; pairs i_t > j_t form a suffix of length b; at most one middle pair is equal, say e ∈ 1. Reflecting the prefix matches gives a palindrome of length 2a+e; reflecting the suffix matches gives one of length 2b+e. The positions remain ordered on each side of the middle. Since max(2a+e, 2b+e) ≥ a+b+e = k, some palindrome is at least as long as the common subsequence. Together with the first bound, the optimal lengths agree.

For example, s = "acbac" and its reverse "cabca" share "abc" of length 3, but "abc" is not a palindrome. The optimal palindrome length is also 3 (for example "aba"). The code returns only the length. To return a palindrome witness, use a palindrome-preserving reconstruction, such as interval DP, rather than an arbitrary LCS witness.

def longest_palindrome_subseq(s: str) -> int:
    return lcs(s, s[::-1])            # reuse the LCS we already wrote
 
assert longest_palindrome_subseq("bbbab") == 4   # "bbbb"
assert longest_palindrome_subseq("cbbd") == 2    # "bb"

• Complexity: O(n²) time and space (LCS of two length-n strings).
• Follow-up they escalate to: do it with an interval DP directly (dp[i][j] over substring s[i..j]) and reduce space. Both are fine; leading with the reduction shows range.

Worked variant — patience-sorting LIS, annotated

The O(n log n) version is short enough to memorise and therefore easy to misexplain. Write it with the invariant in the comments so the explanation comes with the code.

from bisect import bisect_left
 
def lis_nlogn(nums: list[int]) -> int:
    # INVARIANT: tails[k] = the SMALLEST possible tail value among all
    # increasing subsequences of length k+1 seen so far.
    # tails is strictly increasing, which is what licenses binary search.
    tails = []
    for x in nums:
        i = bisect_left(tails, x)     # first index with tails[i] >= x
        if i == len(tails):
            tails.append(x)           # x extends the longest chain by one
        else:
            tails[i] = x              # x is a BETTER (smaller) tail for length i+1
    return len(tails)                  # length only — tails is NOT the subsequence

The two claims you must be able to defend on the spot:

Why tails stays sorted. Appending means x exceeds every stored tail. For a replacement at i, x ≤ the old tails[i], and when i > 0 the lower-bound search also gives tails[i−1] < x. The next entry, if any, exceeds the old tails[i] and therefore x. At i = 0 there is no left-neighbour condition; do not read tails[-1] as one.

Why the length is the answer even though the entries need not share a witness. tails is a length-indexed record of best-possible endings, not a real subsequence. Replacing a tail never shortens any chain — it only makes future extension easier by lowering the bar. So len(tails) can never overstate the LIS, and since every element gets a chance to extend, it can never understate it either. Say this explicitly; "the array is not the answer, its length is" is the sentence that separates understanding from recall.

Strict versus non-strict. bisect_left gives strictly increasing. For non-decreasing (ties allowed) switch to bisect_right. One function name, entirely different problem — read the statement twice before choosing.

Common failure modes

1. Reading dp[-1] instead of max(dp) in the O(n²) LIS. The single most common bug in this family; it passes on inputs where the best chain happens to end last.
2. Initialising the LIS dp array to 0 rather than 1. Every element is an increasing subsequence of length one all by itself.
3. Off-by-one in the LCS grid. dp has dimensions (m+1) × (n+1), so dp[i][j] compares a[i-1] with b[j-1]. Indexing the strings with i and j directly is the classic slip.
4. Treating tails as the actual subsequence. It frequently is not, and printing it produces a plausible-looking wrong answer.
5. Using bisect_right when the problem said strictly increasing. This computes a longest non-decreasing subsequence instead. On [2, 2, 2] it gives 3 instead of 1; the error is not a universal function of the longest consecutive duplicate run.
6. Forgetting the height tie-break in Russian Doll Envelopes. Sorting both keys ascending lets the LIS pick two envelopes of identical width, which do not nest.

Tradeoff

Decision: For LIS, which implementation do you reach for under a tight review?

Name: O(n^2) DP

Gain: Trivial to derive on the spot, easy to reconstruct the actual subsequence with parent pointers, hard to get wrong.

Cost: Too slow if n is up to 1e5.

Pick: when n is small (≤ a few thousand) or a reviewer also wants the subsequence itself.

Name: O(n log n) patience sorting

Gain: Fast enough for n up to 1e5+, and it is the 'expected' answer for LC300.

Cost: Reconstruction needs extra bookkeeping; the tails array is easy to misexplain.

Pick: when constraints show large n, or after you have given the n^2 version and they ask for better.

Verdict: State the O(n^2) DP to prove understanding, then offer O(n log n). Never lead with patience sorting cold — if you fumble the tails explanation you look like you memorised it.

In practice

For a sequence comparison allowing only insertions and deletions at unit cost, an LCS of length L yields edit count m + n − 2L: delete the unmatched elements of the first sequence and insert those missing from the second. Any such edit script retains a common subsequence, proving minimality. This is a model for line-based diffs, not a claim that every diff tool or setting returns that particular optimum. With unit-cost substitutions, the formula no longer applies: changing "a" to "b" costs 1 substitution but 2 insert/delete operations.

You are ready to move on when you can

• Write the O(n^2) LIS DP from memory and explain why the answer is max(dp), not dp[-1].

• Explain why patience sorting's tails-length equals the LIS length, and admit tails is not the subsequence.

• Write the LCS grid DP and state the match vs mismatch branches from first principles.

• Reduce Longest Palindromic Subsequence to LCS(s, reverse(s)) unprompted.

• Name the descending-height tie-break in Russian Doll Envelopes and say why it is needed.

Self-check (answer follows each question).

Check yourself

Q: In the LIS DP, why is the answer max(dp) rather than dp[n-1]?

A: Because the longest increasing chain can end at any index, not necessarily the last element. dp[i] is defined as the best chain ENDING at i, so the global best is the maximum over all endpoints.

Q: In LCS, when the last two characters match, why do we go to dp[i-1][j-1] + 1 and not, say, max of the neighbours?

A: Matching a shared last character is provably never worse than skipping it (exchange argument), so we commit to the match: extend the LCS of the two shorter prefixes by one.

Q: How does Longest Palindromic Subsequence reduce to LCS?

A: The optimal lengths are equal, as the two bounds in the worked reduction show. An arbitrary common subsequence is not necessarily palindromic: abc is a length-3 LCS of acbac and cabca. Use interval DP or a palindrome-preserving reconstruction when the actual palindrome is requested.

Q: What is stored in the patience-sorting tails array, and what is its length?

A: tails[k] holds the smallest possible tail value of an increasing subsequence of length k+1. Its length equals the LIS length. Its contents are NOT the LIS itself.

Q: In the O(n log n) LIS, what exactly does tails[k] hold, and why does replacing a tail never lose an answer?

A: tails[k] is the smallest tail value over all increasing subsequences of length k+1. Overwriting it with a smaller value cannot shorten any existing chain — the chain of that length still exists — it only lowers the bar for future extension. So the length is preserved and future chances improve.

Q: You need non-decreasing rather than strictly increasing. What single change do you make?

A: Swap bisect_left for bisect_right. bisect_left finds the first tail >= x and overwrites it, forbidding ties; bisect_right finds the first tail > x, so equal values are allowed to extend.

Q: Why is the LCS table (m+1) x (n+1) rather than m x n?

A: The extra row and column encode the empty-prefix base cases, which are all zero. Without them every access to dp[i-1][j-1] at the boundary needs a special case, and that is where the off-by-one bugs come from.

Q: In Russian Doll Envelopes, why sort width ascending but height DESCENDING within equal widths?

A: So that two envelopes of equal width can never both be picked by the subsequent LIS-on-heights (a strictly increasing height run can't take two equal-width items), enforcing strict nesting on both dimensions.

Stretch: true

Practice queue

Solve in this order; log each as cold / warm / hint / failed for your spaced queue.

1. LC300 Longest Increasing Subsequence — the parent; do both n² and n log n.
2. LC1143 Longest Common Subsequence — the other parent; then add rolling-row space reduction.
3. LC516 Longest Palindromic Subsequence — reduce to LCS.
4. LC1035 Uncrossed Lines — LCS in disguise.
5. LC673 Number of Longest Increasing Subsequences — LIS with counts.
6. LC354 Russian Doll Envelopes — sort + LIS, the boss of this session.

• Two parent problems — LIS (one array, monotone) and LCS (two strings, aligned) — generate a dozen mediums.

• LIS answer is max(dp); LCS matches on the diagonal corner. That's the one detail each family hides.

• Know LIS in both O(n^2) and O(n log n); lead with the DP, offer patience sorting as the follow-up.

• Reductions are the real skill: palindromic subsequence → LCS(s, reverse(s)); envelopes → sort then LIS.

Corrective source notes

• Python 3.14 bisect_left — the returned boundary separates values less than x from values greater than or equal to x. Freshly checked 2026-10-09.

• Longest increasing subsequence - Algorithms for Competitive Programming — The efficient LIS table stores the smallest achievable ending value for each subsequence length. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.