---
title: Longest Increasing Subsequence
module: Dynamic Programming
moduleNumber: 8
lessonNumber: 3
order: 803
summary: |
  Given a sequence of numbers, how long is its longest strictly increasing
  subsequence? A first dynamic program indexes subproblems by the element each
  subsequence _ends at_, giving an $O(n^2)$ solution with parent-pointer
  reconstruction. A sharper idea, the patience-sorting _tails_ array searched by
  binary search, drops the time to $O(n\log n)$. We then fold in the
  variants: non-decreasing, counting, Russian-doll envelopes, and bitonic.
topics: [Dynamic Programming]
sources:
  - book: CLRS
    ref: "Ch. 15 — Dynamic Programming (Problem 15-4)"
  - book: Skiena
    ref: "§ — Longest Increasing Subsequence"
  - book: Erickson
    ref: "Ch. — Dynamic Programming"
practice:
  - title: 'Longest Increasing Subsequence'
    slug: longest-increasing-subsequence
    difficulty: Medium
  - title: 'Number of Longest Increasing Subsequence'
    slug: number-of-longest-increasing-subsequence
    difficulty: Medium
  - title: 'Russian Doll Envelopes'
    slug: russian-doll-envelopes
    difficulty: Hard
  - title: 'Longest Increasing Subsequence II'
    slug: longest-increasing-subsequence-ii
    difficulty: Hard
  - title: 'Maximum Height by Stacking Cuboids'
    slug: maximum-height-by-stacking-cuboids
    difficulty: Hard
---

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 < \cdots < i_k$ whose
values strictly increase, $a[i_1] < a[i_2] < \cdots < 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$.[^skiena-lis]

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

$$
% caption: 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.
\begin{tikzpicture}[
  >=Stealth, x=7mm, y=3.4mm,
  dot/.style={circle, draw, fill=white, inner sep=0pt, minimum size=4pt},
  pick/.style={circle, draw=acc, fill=acc!15, very thick, inner sep=0pt, minimum size=5.5pt}]
  \definecolor{acc}{HTML}{2348F2}
  % axes
  \draw[->, black] (-0.3,0) -- (8.4,0) node[right, font=\footnotesize, black] {position};
  \draw[->, black] (-0.3,0) -- (-0.3,10.3) node[above, font=\footnotesize, black] {value};
  % points (pos i, value a[i]); chain on indices 1,3,5,6 -> values 3,4,5,9
  \coordinate (p1) at (1,3);
  \coordinate (p2) at (2,1);
  \coordinate (p3) at (3,4);
  \coordinate (p4) at (4,1);
  \coordinate (p5) at (5,5);
  \coordinate (p6) at (6,9);
  \coordinate (p7) at (7,2);
  \coordinate (p8) at (8,6);
  % the rising chain, drawn behind the dots
  \draw[acc, very thick] (p1) -- (p3) -- (p5) -- (p6);
  \foreach \p in {p2,p4,p7,p8} \node[dot] at (\p) {};
  \foreach \p in {p1,p3,p5,p6} \node[pick] at (\p) {};
  % value labels above each point
  \foreach \p/\v in {p1/3,p2/1,p3/4,p4/1,p5/5,p6/9,p7/2,p8/6}
    \node[font=\scriptsize, black!70, above=2pt] at (\p) {$\v$};
\end{tikzpicture}
$$

A brute-force scan over all $2^n$ subsequences is hopeless. But LIS has clean
[optimal substructure](/algorithms/dynamic-programming/principles),
the same property behind every dynamic program, and it admits two algorithms worth knowing
well: a direct $O(n^2)$ dynamic program, and a faster $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.

> **Definition (LIS subproblem).** Let $L[i]$ be the length of the longest increasing subsequence of $a[1..i]$
> that ends at index $i$ (so it must include $a[i]$).

Every increasing subsequence ends _somewhere_, so the answer is
$\max_{1 \le i \le 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\parens{\{\,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.

> **Correctness (induction on $i$).** Assume $L[j]$ is correct for every $j < i$.
> Let $S$ be a longest increasing subsequence ending at $i$. If $S = (a[i])$ then
> $|S| = 1$, matched by the $\{0\}$ branch. Otherwise $S$ has a second-to-last
> element at some index $j < i$ with $a[j] < a[i]$, and $S$ minus its last element
> is an increasing subsequence ending at $j$, so $|S| - 1 \le L[j]$ by the IH;
> hence $|S| \le L[j] + 1$. Conversely, taking the longest subsequence ending at
> the maximizing $j$ and appending $a[i]$ exhibits a valid subsequence of length
> $L[j] + 1$. Both directions give equality. $\qed$

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

```algorithm
caption: $\textsc{LIS-Quadratic}(a[1..n])$ — length and parent pointers
number: 1
for $i \gets 1$ to $n$ do
  $L[i] \gets 1$ ; $\ \mathit{prev}[i] \gets \text{nil}$ // singleton
  for $j \gets 1$ to $i - 1$ do
    if $a[j] < a[i]$ and $L[j] + 1 > L[i]$ then
      $L[i] \gets L[j] + 1$
      $\mathit{prev}[i] \gets j$ // best predecessor
$\mathit{best} \gets \arg\max_i L[i]$
return $L[\mathit{best}]$ and the chain $\mathit{best}, \mathit{prev}[\mathit{best}], \dots$
```

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

$$
% caption: Parent pointers for $a=[3,1,4,1,5,9,2,6]$. Following $\mathit{prev}$ back from
%          the best endpoint (index $6$, $L=4$) yields $3\to4\to5\to9$.
\begin{tikzpicture}[
  >=Stealth,
  cell/.style={draw, minimum size=9mm, inner sep=1pt, font=\small},
  pick/.style={cell, draw=acc, very thick},
  lbl/.style={draw=none, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[pick] (c1) at (0,0) {3};
  \node[cell] (c2) at (1,0) {1};
  \node[pick] (c3) at (2,0) {4};
  \node[cell] (c4) at (3,0) {1};
  \node[pick] (c5) at (4,0) {5};
  \node[pick] (c6) at (5,0) {9};
  \node[cell] (c7) at (6,0) {2};
  \node[cell] (c8) at (7,0) {6};
  \foreach \i/\x in {1/0,2/1,3/2,4/3,5/4,6/5,7/6,8/7}
    \node[lbl, gray] at (\x,0.7) {$\i$};
  \foreach \v/\x in {1/0,1/1,2/2,1/3,3/4,4/5,2/6,4/7}
    \node[font=\small] at (\x,-1.5) {$\v$};
  \node[lbl, gray] at (-1.15,-1.5) {$L[i]$};
  % prev hops 6 -> 5 -> 3 -> 1, arcing below the cells, clear of the L[i] row
  \draw[->, acc, thick] (c6.south) to[bend left=48] (c5.south);
  \draw[->, acc, thick] (c5.south) to[bend left=32] (c3.south);
  \draw[->, acc, thick] (c3.south) to[bend left=32] (c1.south);
\end{tikzpicture}
$$

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

$$
% caption: One $L=4$ chain $3\to4\to5\to9$ (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.
\begin{tikzpicture}[
  cell/.style={draw, minimum size=9mm, inner sep=1pt, font=\small},
  pick/.style={cell, draw=acc, very thick},
  alt/.style={cell, draw=acc, thick, dashed},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  \node[pick] (c1) at (0,0) {3};
  \node[alt]  (c2) at (1,0) {1};
  \node[pick] (c3) at (2,0) {4};
  \node[cell] (c4) at (3,0) {1};
  \node[pick] (c5) at (4,0) {5};
  \node[pick] (c6) at (5,0) {9};
  \node[cell] (c7) at (6,0) {2};
  \node[alt]  (c8) at (7,0) {6};
  \foreach \i/\x in {1/0,2/1,3/2,4/3,5/4,6/5,7/6,8/7}
    \node[font=\scriptsize, gray] at (\x,1.45) {$\i$};
  \foreach \v/\x in {1/0,1/1,2/2,1/3,3/4,4/5,2/6,4/7}
    \node[font=\small] at (\x,-0.85) {$\v$};
  \node[font=\scriptsize, gray] at (-1.05,-0.85) {$L[i]$};
  % chosen chain 3 -> 4 -> 5 -> 9 (greedy: earliest predecessor at each tie)
  \draw[->, acc, thick] (c1.north) to[bend left=28] (c3.north);
  \draw[->, acc, thick] (c3.north) to[bend left=30] (c5.north);
  \draw[->, acc, thick] (c5.north) to[bend left=36] (c6.north);
  % the tie at the START: 4 could instead extend the 1 at index 2 (dotted = the other option)
  \draw[->, acc, dotted, thick] (c2.south) to[bend right=30] (c3.south);
  \node[font=\scriptsize, acc] at (1.6,-1.55) {or start at the $1$ (index $2$)};
  % the free choice at the END (drawn below, like the start alternative): equally long ending at the 6,
  % dipping under the L[i] row so it clears those digits
  \draw[->, acc, dotted, thick] (c5.south) to[bend right=58] (c8.south);
  \node[font=\scriptsize, acc] at (5.9,-2.05) {or end at the $6$ (index $8$)};
\end{tikzpicture}
$$

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:**
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 $\mathit{prev}$ has ties or several
endpoints reach the maximum length, the LIS is simply not unique.

::impl{algo="lis_quadratic"}

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

The quadratic inner loop searches _all_ earlier indices for the best predecessor.
To remove it, stop tracking endpoints individually and instead
maintain, for each achievable length, the single most useful witness.

> **Definition (Tails array).** Let $\mathit{tails}[k]$ = the **smallest possible last element** of any increasing
> subsequence of length $k+1$ seen so far (zero-indexed $k$).

The whole algorithm is one pass. For each element $x = a[i]$,
[binary-search](/algorithms/sequences/binary-search-on-the-answer)
$\mathit{tails}$ for the first entry $\ge 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 $\mathit{tails}$.

```algorithm
caption: $\textsc{LIS-Patience}(a[1..n])$ — tails array, $O(n\log n)$
number: 2
$\mathit{tails} \gets$ empty array
for $i \gets 1$ to $n$ do
  $k \gets \textsc{Lower-Bound}(\mathit{tails},\ a[i])$ // first $\mathit{tails}[k] \ge a[i]$
  if $k = |\mathit{tails}|$ then
    append $a[i]$ to $\mathit{tails}$ // exceeds all tails: extend
  else
    $\mathit{tails}[k] \gets a[i]$ // shrink length-$(k{+}1)$ tail
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, **$\mathit{tails}$ is always sorted in
increasing order**, so binary search is valid. Second, **the updates never
reduce any achievable length**, so the array's length tracks the true LIS.

> **Invariant.** After processing any prefix, $\mathit{tails}$ is strictly
> increasing, and $\mathit{tails}[k]$ is the minimum tail over all
> length-$(k+1)$ increasing subsequences of that prefix.

> **Proof.** _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$: $\mathit{tails}[k-1] <
> \mathit{tails}[k]$. An overwrite preserves this. When we replace
> $\mathit{tails}[k]$ by $x$, the `lower_bound` guarantees $\mathit{tails}[k-1] <
> x$ (else $k-1$ would have been the found index) and $x \le \mathit{tails}[k] <
> \mathit{tails}[k+1]$, so the array stays strictly increasing.
>
> _Overwriting never hurts._ Replacing $\mathit{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
> $|\mathit{tails}|$ equals the LIS length. $\qed$

> **Remark (The card game).** The name comes from the solitaire variant **patience
> sorting**: deal cards one at a time onto piles, placing each card on the leftmost
> pile whose top is $\ge$ it, or starting a new pile to the right if none qualifies.
> The top of each pile is a $\mathit{tails}$ entry, and the number of piles at
> the end is the LIS length. The greedy "leftmost legal pile" rule _is_ the
> `lower_bound` overwrite.

$$
% caption: Patience sorting on $a=[3,1,4,1,5,9,2,6]$: the full $\mathit{tails}$ array as each
%          element arrives. Blue marks the cell just written; the right column records whether
%          the step appended (extended the LIS) or overwrote (shrank a tail). The final length
%          $4$ is the LIS length.
\begin{tikzpicture}[
  cell/.style={draw, minimum size=7mm, inner sep=1pt, font=\small},
  hit/.style={cell, draw=acc, very thick},
  >=stealth, node distance=0mm]
  \definecolor{acc}{HTML}{2348F2}
  % rows: y decreases; each row = tails after processing one element
  \node[font=\scriptsize, gray] at (-2.0,0)     {add $3$};
  \node[hit]  at (0,0) {3};
  \node[font=\footnotesize, acc] at (4.6,0)        {\texttt{\texttt{append}}};
  \node[font=\scriptsize, gray] at (-2.0,-0.85)  {add $1$};
  \node[hit]  at (0,-0.85) {1};
  \node[font=\footnotesize, acc] at (4.6,-0.85)     {\texttt{overwrite}};
  \node[font=\scriptsize, gray] at (-2.0,-1.7)   {add $4$};
  \node[cell] at (0,-1.7) {1};  \node[hit] at (0.85,-1.7) {4};
  \node[font=\footnotesize, acc] at (4.6,-1.7)      {\texttt{append}};
  \node[font=\scriptsize, gray] at (-2.0,-2.55)  {add $1$};
  \node[hit] at (0,-2.55) {1};  \node[cell] at (0.85,-2.55) {4};
  \node[font=\footnotesize, acc] at (4.6,-2.55)     {\texttt{overwrite}};
  \node[font=\scriptsize, gray] at (-2.0,-3.4)   {add $5$};
  \node[cell] at (0,-3.4) {1};  \node[cell] at (0.85,-3.4) {4}; \node[hit] at (1.7,-3.4) {5};
  \node[font=\footnotesize, acc] at (4.6,-3.4)      {\texttt{append}};
  \node[font=\scriptsize, gray] at (-2.0,-4.25)  {add $9$};
  \node[cell] at (0,-4.25) {1};  \node[cell] at (0.85,-4.25) {4}; \node[cell] at (1.7,-4.25) {5}; \node[hit] at (2.55,-4.25) {9};
  \node[font=\footnotesize, acc] at (4.6,-4.25)     {\texttt{append}};
  \node[font=\scriptsize, gray] at (-2.0,-5.1)   {add $2$};
  \node[cell] at (0,-5.1) {1};  \node[hit] at (0.85,-5.1) {2}; \node[cell] at (1.7,-5.1) {5}; \node[cell] at (2.55,-5.1) {9};
  \node[font=\footnotesize, acc] at (4.6,-5.1)      {\texttt{overwrite}};
  \node[font=\scriptsize, gray] at (-2.0,-5.95)  {add $6$};
  \node[cell] at (0,-5.95) {1};  \node[cell] at (0.85,-5.95) {2}; \node[cell] at (1.7,-5.95) {5}; \node[hit] at (2.55,-5.95) {6};
  \node[font=\footnotesize, acc] at (4.6,-5.95)     {\texttt{overwrite}};
\end{tikzpicture}
$$

Each row is $\mathit{tails}$ after one more element, with the just-written cell in blue and
the append-or-overwrite verdict on the right. Adding $2$ overwrites the $4$ (the first tail
$\ge 2$): the length-$2$ run now ends at the smaller value $2$, leaving room for future
growth without shortening the array. The final $\mathit{tails} = [1,2,5,6]$ has length $4$,
matching the LIS length. The values in that last row are _not_ themselves an LIS — $[1,2,5,6]$
never occurs in order — but their **count** matches the LIS length, and the index-tracking below
recovers a genuine subsequence.

The one non-trivial step in each iteration is the placement itself: given the sorted
array $\mathit{tails}$ and the incoming $x$, find the first entry $\ge x$. Because
$\mathit{tails}$ is sorted, this `lower_bound` is a textbook binary search, halving the
live window each probe. Adding $2$ into $\mathit{tails} = [1,4,5,9]$ runs as follows.

$$
% caption: Binary search (lower_bound) placing $x=2$ into the sorted $\mathit{tails}=[1,4,5,9]$.
%          The window $[lo,hi)$ halves each probe until it collapses on index $1$ (value $4$),
%          the first tail $\ge 2$; that cell is overwritten by $2$.
\begin{tikzpicture}[
  cell/.style={draw, minimum size=8mm, inner sep=1pt, font=\small},
  hit/.style={cell, draw=acc, very thick, fill=acc!12},
  >=Stealth]
  \definecolor{acc}{HTML}{2348F2}
  % index labels
  \foreach \i/\x in {0/0,1/1,2/2,3/3}
    \node[font=\scriptsize, gray] at (\x,0.75) {\i};
  % the array
  \node[cell] (t0) at (0,0) {1};
  \node[hit]  (t1) at (1,0) {4};
  \node[cell] (t2) at (2,0) {5};
  \node[cell] (t3) at (3,0) {9};
  % probe mid = 2 (value 5): 5 >= 2, so search left half
  \node[font=\footnotesize, acc] at (6.0,0.5) {\texttt{probe} index 2: \texttt{5 $\ge$ 2},};
  \node[font=\scriptsize, acc] at (6.0,0.05) {search the left half};
  \draw[->, acc, thick] (t2.north) to[bend left=48] (4.4,0.6);
  % target found: index 1 value 4, first tail >= 2
  \node[font=\footnotesize, acc] at (6.0,-1.35) {land on index 1: \texttt{4 $\ge$ 2},};
  \node[font=\scriptsize, acc] at (6.0,-1.8) {overwrite 4 with 2};
  \draw[->, acc, thick] (t1.south) to[bend right=22] (4.4,-1.4);
  % result row
  \node[font=\scriptsize, gray] at (-2.0,-2.4) {after:};
  \node[cell] at (0,-2.4) {1};
  \node[hit]  at (1,-2.4) {2};
  \node[cell] at (2,-2.4) {5};
  \node[cell] at (3,-2.4) {9};
\end{tikzpicture}
$$

The search never inspects the whole array: the first probe rules out the right half, so
index $1$ is confirmed as the target after $O(\log|\mathit{tails}|) = O(\log n)$ comparisons.
Overwriting the $4$ with the smaller $2$ keeps the length-$2$ tail as small as possible.

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

::impl{algo="lis_patience"}

## Variants on the same machine

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

**Longest non-decreasing subsequence.** To allow equal adjacent values
($a[i_1] \le a[i_2] \le \cdots$), change `lower_bound` to **`upper_bound`**: search
for the first tail _strictly greater_ than $x$. An equal element then extends rather
than overwrites, giving the non-strict relaxation. (In the $O(n^2)$ DP,
change the test $a[j] < a[i]$ to $a[j] \le a[i]$.)

**Counting the number of LIS.** Alongside $L[i]$ track $\mathit{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 $\mathit{cnt}[i] \gets \mathit{cnt}[j]$; when
a tying predecessor is found ($L[j] + 1 = L[i]$), accumulate
$\mathit{cnt}[i] \mathrel{+}= \mathit{cnt}[j]$. The answer sums $\mathit{cnt}[i]$ over
all $i$ achieving the global maximum $L[i]$. Speeding this counting variant to
$O(n\log n)$ uses a
[Fenwick or segment tree](/algorithms/data-structures/fenwick-and-segment-trees)
keyed by value to roll up best-length-and-count over smaller predecessors.[^lc-count]

**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 what makes this valid: 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)$.[^lc-doll]

**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$.

$$
% caption: 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$.
\begin{tikzpicture}[
  >=Stealth,
  cell/.style={draw, minimum size=9mm, inner sep=1pt, font=\small},
  pk/.style={cell, fill=acc!18},
  lbl/.style={draw=none, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \v/\x/\sty in {1/0/cell,3/1/cell,5/2/pk,4/3/cell,2/4/cell}
    \node[\sty] (c\x) at (\x,0) {$\v$};
  \foreach \v/\x in {1/0,2/1,3/2,3/3,2/4} \node[lbl] at (\x,-0.8) {$\v$};
  \foreach \v/\x in {1/0,2/1,3/2,2/3,1/4} \node[lbl] at (\x,-1.45) {$\v$};
  \node[lbl, gray] at (-1.0,-0.8) {$L[i]$};
  \node[lbl, gray] at (-1.0,-1.45) {$R[i]$};
  \draw[->, acc, thick] (-0.4,0.65) -- (1.6,0.65) node[midway, above, draw=none, font=\scriptsize, acc] {increase};
  \draw[->, acc, thick] (4.4,0.65) -- (2.4,0.65) node[midway, above, draw=none, font=\scriptsize, acc] {decrease};
\end{tikzpicture}
$$

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$.

> **Enrichment — Mirsky's theorem.** Patience sorting is a constructive proof of
> **Mirsky's theorem**: the minimum number of antichains (here, decreasing
> subsequences) needed to cover the sequence equals the length of the longest
> chain (the longest increasing subsequence), which equals the number of
> piles. The dual statement, that the fewest chains covering a poset equals its
> longest antichain, is Dilworth's theorem.

::impl{algo="count_lis,russian_doll_envelopes,bitonic_subsequence"}

## Lower bounds, permutations, and a longer view

The $O(n \log n)$ patience-sorting bound is essentially optimal. Fredman (1975)
proved that any comparison-based LIS
algorithm needs $\Omega(n \log n)$ comparisons in the worst case, so the tails-array
method is asymptotically the best achievable under comparisons — the binary search
is forced. Only by dropping to the integer-RAM model (values
in a bounded range, van Emde Boas or $y$-fast tries in place of binary search) can
one shave the bound to $O(n \log \log n)$; the bounded-gap variant **Longest
Increasing Subsequence II** requires a segment tree over the value axis instead of a
plain tails array.

Patience sorting also appears in probability. Hammersley asked in
1972 how long the LIS of a _random_ permutation of $\{1, \dots, n\}$ tends to be;
the answer, $\approx 2\sqrt{n}$, was determined by Logan and Shepp and by Vershik
and Kerov (1977), and the full limiting distribution of the fluctuations — the
**Tracy–Widom distribution** from random-matrix theory — was found by Baik, Deift,
and Johansson (1999). That an interview-style array problem shares its scaling law
with the largest eigenvalue of a random Hermitian matrix is one of the more
surprising connections in combinatorics, and patience sorting is the constructive
object underneath it (Aldous and Diaconis's 1999 survey "Longest increasing
subsequences: from patience sorting to the Baik–Deift–Johansson theorem" is the
readable entry point).[^lis-beyond]

The chain\/antichain duality noted above (Mirsky and Dilworth) is
the reason LIS generalizes cleanly to **partial orders**: Russian-doll envelopes,
box-stacking (**Maximum Height by Stacking Cuboids**), and job-nesting are all
"longest chain in a poset" problems, and the sort-then-LIS reduction works precisely
when the poset can be linearized on one coordinate so that the residual constraint is
one-dimensional. When it cannot — three or more strictly-independent dimensions —
the problem becomes a longest chain in higher-dimensional dominance order, solvable
with a $k$-dimensional Fenwick tree in $O(n \log^{k-1} n)$, the direct descendant of
the [Fenwick-tree counting](/algorithms/data-structures/fenwick-and-segment-trees)
that speeds up the LIS-counting variant.

## 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
  $\mathit{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 $|\mathit{tails}|$ is the LIS length;
  this is **patience sorting**.
- **Variants** reuse the same algorithms: `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-lis]: **Skiena**, § — Longest Increasing Subsequence: LIS as a canonical sequence DP, with the $O(n\log n)$ improvement over the naive quadratic fill.
[^lc-count]: **Erickson**, Ch. — Dynamic Programming: augmenting an optimization DP with a parallel count array to enumerate optimal solutions.
[^lc-doll]: **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.
[^lis-beyond]: **Fredman** (1975) for the $\Omega(n\log n)$ comparison lower bound; **Aldous & Diaconis** (1999, _Bull. AMS_), "Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem", surveying the $\approx 2\sqrt{n}$ expected LIS of a random permutation and its Tracy–Widom fluctuations (**Baik, Deift, Johansson**, 1999).