DP problems — Longest Increasing Subsequence (LIS) — O(n²) and O(n log n): Visual walkthrough

We build everything on one running array: $A = [3, 1, 4, 1, 5, 9, 2, 6]$ Nothing else is assumed. Let us define our words before we use them.

Figure — DP problems — Longest Increasing Subsequence (LIS) — O(n²) and O(n log n)

Step 1 — Draw the array as heights, and draw one increasing chain

WHAT. Plot each value $A [i]$ as a dot at horizontal position $i$ and height $A [i]$ . An increasing subsequence is any set of dots you can connect with arrows that always go rightward and upward.

WHY. Height = value, position = index. "Increasing subsequence" now becomes a staircase that only ever climbs as you move right. That visual — a path that never steps down — is the whole problem. Everything below is about building the longest such staircase without ever looking at all $2^{n}$ possible paths.

PICTURE. Figure s01 above. The red arrows connect $3 \to 4 \to 5 \to 9$ (length 4). Notice every arrow points up-and-to-the-right; that is the only rule.

Step 2 — The one bookkeeping array: `tails`

WHAT. We introduce a single array called tails. We read it like this: $tails [k] = the smallest value that can END an increasing chain of length (k + 1) .$ Here $k$ starts at $0$ , so tails[0] is about length-1 chains, tails[1] about length-2 chains, and so on.

WHY the word "smallest". A chain of a given length is only useful for the future if it is easy to extend. To extend a chain by a new value $x$ , we need $x$ to be bigger than the chain's last value. So the smaller that last value (the "tail") is, the more future $x$ 's can attach. Among all chains of the same length, the one with the tiniest tail dominates every other — it accepts everything they accept, and more. That is why we only ever record the minimum tail per length.

PICTURE. Figure s02 shows two different length-2 chains ending in $4$ and in $2$ . The one ending in $2$ (red) is strictly better: any future value that could sit on top of $4$ can also sit on top of $2$ , but not vice-versa.

Step 3 — `tails` is automatically sorted (this is what lets us binary-search)

WHAT. Claim: tails is strictly increasing, i.e. $tails [0] < tails [1] < tails [2] < \dots$ — always, no matter what array we feed in.

WHY. Take any chain of length $k + 1$ ending at value $tails [k]$ . Chop off its last element. You now have a chain of length $k$ whose tail is some value strictly less than $tails [k]$ (it came earlier in a rising chain). But $tails [k - 1]$ is the smallest possible length- $k$ tail, so $tails [k - 1] \leq (that chopped tail) < tails [k] .$ Chain the inequality: $tails [k - 1] < tails [k]$ . Done — the array climbs.

PICTURE. Figure s03: a length-4 red chain; drop its top element and the remaining length-3 chain's tail is provably lower than the length-4 tail. That forces the staircase-of-tails to rise.

Step 4 — Processing one new value $x$ : find where it fits

WHAT. For each incoming value $x$ , we ask: what is the leftmost position $k$ where $tails [k] \geq x$ ? This is the operation called ==lower_bound== — "first slot not smaller than $x$ ".

WHY. Two things can happen and both are decided by that position:

If such a $k$ exists, then $x$ can serve as a better (smaller) tail for length- $(k + 1)$ chains, so we overwrite $tails [k] = x$ . We did not make any chain longer — we made an existing length cheaper to extend later.
If no slot is $\geq x$ (i.e. $x$ is bigger than every tail), then $x$ climbs on top of the currently-longest chain and we append it, growing the record length by one.

WHY $\geq$ and not $>$ . We want strictly increasing subsequences. Replacing the first tail that is equal to $x$ prevents a duplicate value from being treated as an extension (a tie is not an increase). If the problem allowed non-decreasing runs, we would search for the first tail strictly $> x$ instead. This one comparison choice is the only difference between the two variants.

PICTURE. Figure s04: the sorted tails array as a number line; the red marker shows lower_bound landing on the first tail $\geq x$ , with the "replace here" arrow.

Step 5 — Watch it run, frame by frame

WHAT. We push all of $A = [3, 1, 4, 1, 5, 9, 2, 6]$ through the rule and record tails after each step.

WHY. Tracing turns the abstract rule into muscle memory, and it surfaces the two interesting moves — a replace that lowers a tail and an append that grows the length.

$x$	leftmost tail $\geq x$ ?	action	`tails` after
3	none	append	`[3]`
1	$3 \geq 1$ at $k = 0$	replace	`[1]`
4	none	append	`[1,4]`
1	$1 \geq 1$ at $k = 0$	replace	`[1,4]`
5	none	append	`[1,4,5]`
9	none	append	`[1,4,5,9]`
2	$4 \geq 2$ at $k = 1$	replace	`[1,2,5,9]`
6	$9 \geq 6$ at $k = 3$	replace	`[1,2,5,6]`

Final length $= len (tails) = 4$ . ✓

PICTURE. Figure s05 overlays the growing tails staircase across these frames; the red segment is the value being replaced/appended at each moment.

Step 6 — Edge and degenerate cases (never leave the reader stranded)

WHAT + WHY + PICTURE, one row each. Figure s06 shows all four side by side.

Empty array []: the loop never runs, tails stays [], length $= 0$ . Correct — no elements, no subsequence.
Strictly decreasing [5,4,3,2,1]: every $x$ is $\leq$ everything in tails, so every step replaces position $0$ . tails never grows past length $1$ → $L = 1$ . Correct: the longest rising chain is any single element.
Strictly increasing [1,2,3,4,5]: nothing is ever $\geq x$ that could block, every $x$ appends → tails grows every step → $L = n$ . Correct: the whole array already rises.
All equal [7,7,7,7]: for strict LIS we use $\geq$ , so each $7$ finds the existing $7$ at $k = 0$ and replaces it, never appending → $L = 1$ . Correct: equal values are not an increase. (Under non-decreasing rules with $>$ , this would give $L = 4$ — that is exactly why the $\geq$ vs $>$ choice matters.)

Recall Why does the decreasing case never append?

Append happens only when $x$ exceeds all current tails. In a decreasing array each new $x$ is smaller than everything seen, so lower_bound always lands at position $0$ and we replace — length stays $1$ .

The one-picture summary

This final figure fuses the whole derivation: the raw array as heights (top), the sorted tails staircase we maintain (middle, red = the smallest-tail invariant), and the single decision box (bottom) — lower_bound, then replace-or-append. The number of steps we ever append equals $L$ , and because tails is forced-sorted (Step 3) each decision costs only $O (lo g n)$ .

Recall Feynman: tell the whole walkthrough to a 12-year-old

Line up your cards left to right. You keep a row of piles. When a new card comes, walk your piles from the left and drop the card on the first pile whose top is not smaller than your card — you cover that top with your (smaller-or-equal) card. If no pile can take it (your card beats every top), start a brand-new pile on the right. Why cover with the smaller card? Because a smaller top is easier for future cards to beat, so more cards can pile up later. At the end, count your piles — that count is the length of the longest always-climbing line of cards hidden in your deck. The "first pile from the left" is just Binary Search on the always-sorted row of pile-tops, and that is the whole $O (n lo g n)$ trick — the card game is Patience Sorting.

Connections

Binary Search — the sorted-tails invariant (Step 3) is what makes lower_bound legal.
Patience Sorting — the card-pile picture in the Feynman retelling.
Dynamic Programming — the $O (n^{2})$ cousin that this fast method optimizes.
Greedy Algorithms — "keep smallest tails" is a greedy exchange argument, proven in Step 2.
Longest Common Subsequence (LCS) — a related subsequence problem.
Russian Doll Envelopes — a 2D application layered on top of LIS.