Longest Increasing Subsequence

Given a sequence of numbers — say 3, 1, 4, 1, 5, 9, 2, 6 — the longest increasing subsequence (LIS) is the longest chain you can pick from them (in order, without rearranging) so each picked number is strictly larger than the previous. For that example the answer is 1, 4, 5, 9 or 1, 2, 6, both of length 4.

The problem sounds like a puzzle. You could try every subset: $2^{n}$ possibilities for n numbers. For 50 numbers that's already more combinations than there are atoms in a grain of sand — obviously impractical.

A smarter approach uses dynamic programming: work left to right, keeping for each position the length of the longest increasing subsequence ending there. That costs $O(n^{2})$ time and solves the problem. But there is something even cleverer hiding behind the scenes — a connection to a card game called patience sorting that slashes the cost to $O(n \log n)$.

In patience sorting each number is dealt left-to-right onto piles following one rule: place it on the leftmost pile whose top is greater than or equal to the number, or start a new pile if none qualifies. The number of piles at the end equals the LIS length.

<p class="hint">{{hint}}</p>
<div class="seq-display" id="seqDisplay"></div>
<div class="piles-area" id="pilesArea"></div>
<div class="status" id="status">{{press_to_begin}}</div>
<div class="btns">
  <button id="btnStep" type="button">{{btn_step}}</button>
  <button id="btnRun" type="button">{{btn_run}}</button>
  <button id="btnLis" type="button" disabled>{{btn_show_lis}}</button>
  <button id="btnBrute" type="button">{{btn_brute}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.seq-display { display: flex; flex-wrap: wrap; gap: 4px; margin-bottom: .6rem; }
.num { width: 36px; height: 36px; display: flex; align-items: center; justify-content: center;
       font: 700 15px ui-monospace, monospace; border-radius: 6px; border: 1.5px solid #cdd9e3;
       background: #e8eef3; color: #1d3557; transition: background .2s; }
.num.current { background: #f4a261; border-color: #e08a40; color: #fff; }
.num.done { background: #c9ccd1; border-color: #adb1b8; color: #555; }
.num.lis-highlight { background: #2a9d8f; border-color: #21867a; color: #fff; }
.piles-area { display: flex; gap: 10px; align-items: flex-end; min-height: 160px;
              border: 1px solid #cdd9e3; border-radius: 8px; padding: 8px; background: #f7f9fb;
              flex-wrap: wrap; margin-bottom: .5rem; }
.pile { display: flex; flex-direction: column-reverse; gap: 3px; align-items: center; }
.pile-label { font-size: .7rem; color: #888; margin-top: 3px; }
.pile-card { width: 36px; height: 36px; display: flex; align-items: center; justify-content: center;
             font: 700 14px ui-monospace, monospace; border-radius: 6px;
             border: 1.5px solid #adb1b8; background: #d5dce3; color: #1d3557; }
.pile-card.top { background: #1d3557; border-color: #1d3557; color: #fff; }
.pile-card.lis-card { background: #2a9d8f; border-color: #21867a; color: #fff; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .45; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Click Step to deal one card at a time and watch the piles form. Click Run All to see the full sort, then Show LIS to highlight one longest increasing subsequence traced back through the piles. Notice that the pile tops always stay sorted — that's what makes binary search work and keeps the algorithm in $O(n \log n)$.

Compare this to the naive approach: press Brute Force to count every subset. For 12 numbers the algorithm checks 4096 subsets; patience sorting takes only 12 binary-search steps.

How hard is the LIS problem, and why does patience sorting hit the sweet spot?

• Brute force checks all $2^{n}$ subsets — hopeless for large n.
• Dynamic programming computes, for each index i, the LIS length ending at i by scanning all j < i. That's $O(n^{2})$ time and $O(n)$ space.
• Patience sorting (also called the patience solitaire algorithm) achieves $O(n \log n)$ time. Each new number is placed with a binary search over the currently sorted pile tops — $O(\log n)$ per element, $O(n)$ total space.
• Is $O(n \log n)$ optimal? For comparison-based algorithms, yes. Deciding whether the LIS length exceeds k is equivalent to sorting the sequence in a restricted sense; any comparison-based algorithm must use Ω(n log n) comparisons.
• Dilworth's theorem gives a beautiful combinatorial lens: in any partially ordered set, the minimum number of chains needed to cover all elements equals the maximum antichain size. For a number sequence this means the number of patience piles equals the LIS length — a non-trivial fact that explains why the card game works.

The solved status: LIS is solved in $O(n \log n)$ — this is a well-established result due to Schensted (1961) and popularized through the connection to patience sorting by Aldous and Diaconis (1999). It is not NP-hard, not undecidable, not open — it is one of the most satisfying complete algorithmic stories in combinatorics.

Related variants are harder: counting the number of distinct LIS is #P-hard, and the sequence alignment problem (longest common subsequence of two strings) sits in $O(nm)$ but resists sub-quadratic solutions for general alphabets.

The longest increasing subsequence is not just a puzzle — it is an engine powering real systems:

• Diff and version control: computing the diff between two files is equivalent to finding the longest common subsequence (LCS) of their lines. LCS reduces to LIS when one sequence is a permutation of the other, which is exactly the common case in code changes.
• Stock market analysis: finding the longest run of rising closing prices in a series is a direct LIS query. Variants drive momentum indicators.
• RNA secondary structure: predicting which bases in an RNA strand pair without crossing requires finding a longest non-crossing matching — a problem closely related to LIS.
• Scheduling: given jobs with release times and deadlines, finding the maximum number of non-overlapping jobs is equivalent to finding the LIS of the sorted job list.
• Patience sort itself: the dealing phase of patience sorting is used in practice as a fast pre-processing step in some external sorting algorithms, because it naturally identifies already-sorted runs.

Understand LIS and you have a template for dozens of "find the longest compatible chain" problems that arise in data processing, bioinformatics, and operations research. It also connects to dynamic programming thinking — every DP problem asks "what is the best we can build, given what came before?"

The longest increasing subsequence starts as a puzzle you could brute-force badly, improves with dynamic programming to $O(n^{2})$, and then patience sorting delivers a beautiful $O(n \log n)$ algorithm that feels almost like magic — until Dilworth's theorem explains exactly why it works.

It is a rare algorithmic story where the final answer is not just fast but understandable: deal your numbers like cards, let the pile tops guide you with binary search, count the piles. That's it.

Next time you run git diff or watch a stock chart, the same idea is quietly at work — finding the longest chain of values that rise in order, one binary search at a time.