Longest Increasing Subsequence

The previous lesson aligned two sequences. Now we ask a question about a single one. Given an array $a [1.. n]$ of numbers, a longest increasing subsequence (LIS) is a longest set of positions $i_{1} < i_{2} < \dots < i_{k}$ whose values strictly increase, $a [i_{1}] < a [i_{2}] < \dots < a [i_{k}]$ . As with LCS, the word is subsequence, not substring: the chosen elements keep their original order but need not be contiguous. In $a = [3, 1, 4, 1, 5, 9, 2, 6]$ the subsequence $[3, 4, 5, 9]$ increases and has length $4$ , and no longer one exists, so the LIS length is $4$ .¹

Plot the values against their positions and an LIS is a longest chain of points that climbs as it moves right, never stepping down:

Values of

a = [3, 1, 4, 1, 5, 9, 2, 6]

plotted against position. An LIS is a longest left-to-right chain that strictly rises; the highlighted path

3, 4, 5, 9

(length

4

) is one such chain.

A brute-force scan over all $2^{n}$ subsequences is hopeless. But LIS has clean optimal substructure, the same optimal-substructure lever behind every dynamic program, and it admits two algorithms worth knowing well: a direct $O (n^{2})$ dynamic program, and a slicker $O (n log n)$ method built on patience sorting.

The $O (n^{2})$ dynamic program: subsequences that end here

The decisive modeling move, the analog of LCS's index by prefix, is to index each subproblem by the element its subsequence is forced to end at. Anchoring the endpoint is what makes the pieces compose: an increasing subsequence ending at $i$ is some shorter increasing subsequence ending at an earlier, smaller element, with $a [i]$ tacked on.

Every increasing subsequence ends somewhere, so the answer is $max_{1 \leq i \leq n} L [i]$ , not $L [n]$ , a small but important distinction from the prefix DPs, where the answer sat in the last cell.

To extend a subsequence so that it ends at $i$ , look at all earlier indices $j < i$ whose value is smaller than $a [i]$ ; any increasing subsequence ending at such a $j$ can be lengthened by appending $a [i]$ . We take the best such predecessor, or start fresh with just $a [i]$ if none exists:

L [i] = 1 + max ({0} \cup {L [j] : j < i, a [j] < a [i]}) .

The ${0}$ guarantees the $max$ is defined and yields $L [i] = 1$ when no smaller predecessor exists: the subsequence consisting of $a [i]$ alone.

Each $L [i]$ scans the $i - 1$ earlier indices, so the fill is $\sum_{i} (i - 1) = Θ (n^{2})$ time and $Θ (n)$ space.

Algorithm 1:

\textsc{LIS-Quadratic}(a[1..n])

— length and parent pointers

1
for $i \gets 1$ to $n$ do
2
$L[i] \gets 1$ ; $\ \mathit{prev}[i] \gets \text{nil}$
singleton
3
for $j \gets 1$ to $i - 1$ do
4
if $a[j] < a[i]$ and $L[j] + 1 > L[i]$ then
5
$L[i] \gets L[j] + 1$
6
$\mathit{prev}[i] \gets j$
best predecessor
7
$\mathit{best} \gets \arg\max_i L[i]$
8
return $L[\mathit{best}]$ and the chain $\mathit{best}, \mathit{prev}[\mathit{best}], \dots$

Reconstruction. The $prev$ array is a forest of parent pointers: to recover an actual LIS, find the index $best$ maximizing $L$ , then follow $prev$ backwards until it hits nil, reversing the collected indices. This costs $O (k) \leq O (n)$ , cheap beside the fill.

Parent pointers for

a = [3, 1, 4, 1, 5, 9, 2, 6]

. Following

prev

back from the best endpoint (index

6

L = 4

) yields

3 \to 4 \to 5 \to 9

The blue endpoints form the recovered chain: starting at the best $L = 4$ cell (index $6$ , value $9$ ) and hopping along $prev$ visits indices $6 \to 5 \to 3 \to 1$ , whose values $9, 5, 4, 3$ reverse to the LIS $3, 4, 5, 9$ .

One

L = 4

chain

3 \to 4 \to 5 \to 9

(indices

1, 3, 5, 6

), arrows along the cell tops. The dotted arrows show equally-long alternatives — starting at the

1

(index

2

), or ending at the

6

(index

8

) instead of the

9

— so the LIS is not unique.

The solid chain $3 \to 4 \to 5 \to 9$ (indices $1, 3, 5, 6$ ) realizes $L = 4$ at index $6$ , and the row beneath records every $L [i]$ . A subtlety worth naming: the predecessor of $4$ is not unique — both the $3$ (index $1$ ) and the $1$ (index $2$ ) are smaller and end a length- $1$ run, so either could precede it. Reconstruction is greedy: it stores and follows a single parent, and we take the earlier index, giving $3, 4, 5, 9$ . The dotted arrows mark the other choices: extending the $1$ at index $2$ instead yields $1, 4, 5, 9$ , and stopping at the $6$ (index $8$ , also $L = 4$ ) yields $3, 4, 5, 6$ . Whenever $prev$ has ties or several endpoints reach the maximum length, the LIS is simply not unique.

The $O (n log n)$ method: patience sorting and the tails array

The quadratic inner loop searches all earlier indices for the best predecessor. The trick that removes it is to stop tracking endpoints individually and instead maintain, for each achievable length, the single most useful witness.

The whole algorithm is one pass. For each element $x = a [i]$ , binary-search $tails$ for the first entry $\geq x$ (a lower_bound). If one is found, overwrite it with $x$ ; if none is (so $x$ exceeds every tail), append $x$ . The LIS length is the final length of $tails$ .

Algorithm 2:

\textsc{LIS-Patience}(a[1..n])

— tails array,

O(n\log n)

1
$\mathit{tails} \gets$ empty array
2
for $i \gets 1$ to $n$ do
3
$k \gets \textsc{Lower-Bound}(\mathit{tails},\ a[i])$
first $\mathit{tails}[k] \ge a[i]$
4
if $k = |\mathit{tails}|$ then
5
append $a[i]$ to $\mathit{tails}$
exceeds all tails: extend
6
else
7
$\mathit{tails}[k] \gets a[i]$
shrink length- $(k{+}1)$ tail
8
return $|\mathit{tails}|$

Each element costs one $O (log n)$ binary search, for $O (n log n)$ total.

Why this is correct

Two facts carry the whole proof. First, $tails$ is always sorted in increasing order, so binary search is even legal. Second, the updates never reduce any achievable length, so the array's length tracks the true LIS.

Sortedness. A length- $(k + 1)$ increasing subsequence is a length- $k$ one with one more element appended, so the minimum tail of length $k + 1$ strictly exceeds that of length $k$ : $tails [k - 1] < tails [k]$ . An overwrite preserves this. When we replace $tails [k]$ by $x$ , the lower_bound guarantees $tails [k - 1] < x$ (else $k - 1$ would have been the found index) and $x \leq tails [k] < tails [k + 1]$ , so the array stays strictly increasing.

Overwriting never hurts. Replacing $tails [k]$ with a smaller value $x$ can only help: any future element that could have extended a length- $(k + 1)$ subsequence ending at the old, larger tail can still extend the one ending at $x$ , since $x$ is smaller. So no achievable length is ever lost: overwrites only make tails more permissive, never shorter. And appending $x$ when it beats every tail records a genuinely new, longer subsequence. Hence $∣ tails ∣$ equals the LIS length. $□$

Patience sorting /

O (n log n)

: the tails array as elements arrive.

Each row marks the overwrite-or-append position in acc. Adding $2$ overwrites the $4$ (the first tail $\geq 2$ ): the length- $2$ run now ends at the smaller value $2$ , leaving room for future growth without ever shortening the array.

Reconstruction in $O (n log n)$ . As written, $tails$ holds values, not positions, so it loses the actual subsequence. To recover it, store indices: let $tailIdx [k]$ hold the position whose value is $tails [k]$ , and on each step record $parent [i] = tailIdx [k - 1]$ (the index then sitting one pile to the left). Following $parent$ back from $tailIdx [last]$ reconstructs an LIS, exactly as in the quadratic version.

Variants on the same machine

Both algorithms bend to a family of related problems with small edits.

Longest non-decreasing subsequence. To allow equal adjacent values ( $a [i_{1}] \leq a [i_{2}] \leq \dots$ ), change lower_bound to upper_bound: search for the first tail strictly greater than $x$ . An equal element then extends rather than overwrites, which is precisely the non-strict relaxation. (In the $O (n^{2})$ DP, change the test $a [j] < a [i]$ to $a [j] \leq a [i]$ .)

Counting the number of LIS. Alongside $L [i]$ track $cnt [i]$ = the number of longest increasing subsequences ending at $i$ . When a strictly better predecessor $j$ is found ( $L [j] + 1 > L [i]$ ), reset $cnt [i] \leftarrow cnt [j]$ ; when a tying predecessor is found ( $L [j] + 1 = L [i]$ ), accumulate $cnt [i] + = cnt [j]$ . The answer sums $cnt [i]$ over all $i$ achieving the global maximum $L [i]$ . Speeding this counting variant to $O (n log n)$ leans on a Fenwick or segment tree keyed by value to roll up best-length-and-count over smaller predecessors.²

Russian doll envelopes. Each envelope has width $w$ and height $h$ , and one nests in another only if both dimensions are strictly larger; find the longest nesting chain. Reduce to LIS in two dimensions: sort by width ascending, and break ties by height descending, then run LIS on the height sequence alone. The descending tiebreak is the trick: among envelopes of equal width, the descending order makes it impossible for two of them to both appear in an increasing height run (their heights decrease), so we never illegally nest two equal-width envelopes. With distinct widths this reduces a 2-D nesting to a plain 1-D LIS, solvable in $O (n log n)$ .³

Bitonic and longest decreasing. A longest decreasing subsequence is just LIS on the reversed comparison (or on the negated array). A longest bitonic subsequence, one that increases then decreases, is computed by running the ending-here LIS left-to-right to get $L [i]$ and a symmetric decreasing pass right-to-left to get $R [i]$ ; the best bitonic peak at $i$ has length $L [i] + R [i] - 1$ .

Bitonic length at each peak. A forward pass gives

L [i]

(longest increasing ending at

i

), a backward pass gives

R [i]

(longest decreasing starting at

i

); the peak at

5

scores

L + R - 1 = 3 + 3 - 1 = 5

On $[1, 3, 5, 4, 2]$ the peak sits at the value $5$ : three elements climb up to it ( $1, 3, 5$ ) and three descend from it ( $5, 4, 2$ ), and the $- 1$ avoids double-counting the peak, so the whole array is one bitonic run of length $5$ .

Takeaways

The LIS is a longest strictly-increasing subsequence (order preserved, contiguity not required), not a substring.
The $O (n^{2})$ DP indexes by the ending index: $L [i] = 1 + max {L [j] : j < i, a [j] < a [i]}$ , the answer is $max_{i} L [i]$ , and parent pointers reconstruct the subsequence.
The $O (n log n)$ method keeps a sorted tails array where $tails [k]$ is the smallest tail of a length- $(k + 1)$ run; each element triggers a lower_bound overwrite-or-append. Overwriting with a smaller tail never loses an achievable length, so $∣ tails ∣$ is the LIS length; this is patience sorting.
Variants reuse the machine: upper_bound for non-decreasing, parallel counts for the number of LIS, sort-then-LIS with a descending tiebreak for Russian-doll envelopes, and forward+backward passes for bitonic.
LIS equals the minimum antichain (decreasing-subsequence) cover, the pile count, a constructive instance of Mirsky's theorem.

Skiena, § — Longest Increasing Subsequence: LIS as a canonical sequence DP, with the $O (n log n)$ improvement over the naive quadratic fill. ↩
Erickson, Ch. — Dynamic Programming: augmenting an optimization DP with a parallel count array to enumerate optimal solutions. ↩
CLRS, Ch. 15 — Dynamic Programming (Problem 15-4): the longest-increasing-subsequence problem and its $O (n log n)$ solution underpinning multi-dimensional nesting variants. ↩

The O(n2) dynamic program: subsequences that end here

The O(nlogn) method: patience sorting and the tails array

Why this is correct

Variants on the same machine

Takeaways

Footnotes

The $O (n^{2})$ dynamic program: subsequences that end here

The $O (n log n)$ method: patience sorting and the tails array