Introduction

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: 2n2^{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(n2)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(nlog⁡n)O(n \log n).

Try It: Patience Sorting

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">Watch <b>patience sorting</b> find the longest increasing subsequence. Each number goes onto the leftmost pile whose top is &ge; the number, or starts a new pile. The pile count equals the LIS length.</p>
<div class="seq-display" id="seqDisplay"></div>
<div class="piles-area" id="pilesArea"></div>
<div class="status" id="status">Press Step or Run All to begin.</div>
<div class="btns">
  <button id="btnStep" type="button">Step</button>
  <button id="btnRun" type="button">Run All</button>
  <button id="btnLis" type="button" disabled>Show LIS</button>
  <button id="btnBrute" type="button">Brute Force</button>
  <button id="btnReset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Patience sorting for LIS:
// Deal each number onto the leftmost pile whose top >= number (strictly: top >= value
// means we place on the pile whose current top is the smallest top that is >= value).
// Equivalently: binary search for the leftmost pile top >= value. This is equivalent
// The number of piles equals the LIS length (Dilworth / Schensted correspondence).
const SEQ = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
let piles = [];       // piles[i] = array of card values (bottom to top)
let prev = [];        // prev[i][j] = { pileIdx, cardIdx } for LIS traceback
let cursor = 0;
let done = false;
let lisCards = null;  // set of "p,c" strings to highlight

function bsearchPile(val) {
  // Find leftmost pile index whose top >= val. Return -1 if none (new pile).
  let lo = 0, hi = piles.length - 1, ans = -1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    const top = piles[mid][piles[mid].length - 1];
    if (top >= val) { ans = mid; hi = mid - 1; }
    else lo = mid + 1;
  }
  return ans;
}

function dealOne() {
  if (cursor >= SEQ.length) return;
  const val = SEQ[cursor];
  const p = bsearchPile(val);
  let cardIdx;
  if (p === -1) {
    piles.push([val]);
    prev.push([null]);
    cardIdx = 0;
    const pileIdx = piles.length - 1;
  } else {
    piles[p].push(val);
    cardIdx = piles[p].length - 1;
    // predecessor: rightmost pile to the left whose top < val (before dealing)
    let predPile = -1, predCard = -1;
    for (let q = p - 1; q >= 0; q--) {
      const t = piles[q][piles[q].length - 2] !== undefined
        ? piles[q][piles[q].length - 2]
        : piles[q][0]; // use second-from-top if available, else top
      // Actually we want the top of pile q BEFORE we placed on pile p (pile q unchanged)
      const top = piles[q][piles[q].length - 1];
      if (top < val) { predPile = q; predCard = piles[q].length - 1; break; }
    }
    prev[p].push(predPile === -1 ? null : { pi: predPile, ci: predCard });
    // Re-index: last entry corresponds to the card just placed
  }
  cursor++;
  render();
  setStatus(fmt('Dealt %val% → pile %v%. Piles: %length% (LIS length so far: %length%).', { val: val, v: p === -1 ? piles.length : p + 1, length: piles.length }), 'info');
  if (cursor >= SEQ.length) {
    done = true;
    document.getElementById('btnLis').disabled = false;
    setStatus(fmt('Done! %length% piles → LIS length = %length%.', { length: piles.length }), 'ok');
  }
}

function runAll() {
  while (cursor < SEQ.length) dealOne();
}

function showLIS() {
  // Traceback from the top card of the last pile
  lisCards = new Set();
  let pi = piles.length - 1;
  let ci = piles[pi].length - 1;
  while (pi !== null && pi !== -1 && pi !== undefined) {
    lisCards.add(pi + ',' + ci);
    const p = prev[pi][ci];
    if (!p) break;
    pi = p.pi; ci = p.ci;
  }
  // Also highlight sequence numbers in LIS
  computeLisSeqIndices();
  render();
  setStatus(fmt('LIS highlighted in teal (length %size%).', { size: lisCards.size }), 'ok');
}

let lisSeqSet = null;
function computeLisSeqIndices() {
  // Standard O(n log n) LIS with index tracking for sequence highlight
  const tails = []; // tails[i] = smallest tail value for IS of length i+1
  const tailIdx = []; // actual sequence index
  const parentIdx = new Array(SEQ.length).fill(-1);
  const posOf = new Array(SEQ.length).fill(-1);
  for (let i = 0; i < SEQ.length; i++) {
    const v = SEQ[i];
    let lo = 0, hi = tails.length;
    while (lo < hi) { const m = (lo + hi) >> 1; tails[m] < v ? lo = m + 1 : hi = m; }
    tails[lo] = v; tailIdx[lo] = i;
    posOf[i] = lo;
    parentIdx[i] = lo > 0 ? tailIdx[lo - 1] : -1;
  }
  // Traceback
  lisSeqSet = new Set();
  let idx = tailIdx[tails.length - 1];
  while (idx !== -1) { lisSeqSet.add(idx); idx = parentIdx[idx]; }
}

function render() {
  // Sequence row
  const sd = document.getElementById('seqDisplay');
  sd.innerHTML = '';
  SEQ.forEach((v, i) => {
    const d = document.createElement('div');
    d.className = 'num' +
      (i === cursor - 1 && !done ? ' current' : '') +
      (i < cursor - (done ? 0 : 1) ? ' done' : '') +
      (lisSeqSet && lisSeqSet.has(i) ? ' lis-highlight' : '');
    d.textContent = v;
    sd.appendChild(d);
  });
  // Piles
  const pa = document.getElementById('pilesArea');
  pa.innerHTML = '';
  if (piles.length === 0) {
    pa.innerHTML = '<span style="color:#aaa;font-size:.85rem;margin:auto">Piles will appear here.</span>';
    return;
  }
  piles.forEach((pile, pi) => {
    const col = document.createElement('div');
    col.className = 'pile';
    const lbl = document.createElement('div');
    lbl.className = 'pile-label';
    lbl.textContent = fmt('Pile %pi%%v%', { pi: pi, v: 1 });
    col.appendChild(lbl);
    pile.forEach((val, ci) => {
      const card = document.createElement('div');
      const isTop = ci === pile.length - 1;
      const isLis = lisCards && lisCards.has(pi + ',' + ci);
      card.className = 'pile-card' + (isTop ? ' top' : '') + (isLis ? ' lis-card' : '');
      card.textContent = val;
      col.appendChild(card);
    });
    pa.appendChild(col);
  });
}

function bruteForce() {
  const n = SEQ.length;
  let best = 0, checked = 0;
  for (let mask = 0; mask < (1 << n); mask++) {
    checked++;
    const sub = [];
    for (let i = 0; i < n; i++) if (mask & (1 << i)) sub.push(SEQ[i]);
    let inc = true;
    for (let i = 1; i < sub.length; i++) if (sub[i] <= sub[i - 1]) { inc = false; break; }
    if (inc && sub.length > best) best = sub.length;
  }
  setStatus(fmt('Brute force checked %checked% subsets. LIS = %best%.', { checked: checked.toLocaleString(), best: best }), 'ok');
  console.log('Brute force: checked', checked, 'subsets, LIS =', best);
}

function reset() {
  piles = []; prev = []; cursor = 0; done = false; lisCards = null; lisSeqSet = null;
  document.getElementById('btnLis').disabled = true;
  render();
  setStatus('Press Step or Run All to begin.', '');
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t; s.className = 'status ' + (cls || '');
}

document.getElementById('btnStep').addEventListener('click', () => { if (!done) dealOne(); });
document.getElementById('btnRun').addEventListener('click', runAll);
document.getElementById('btnLis').addEventListener('click', showLIS);
document.getElementById('btnBrute').addEventListener('click', bruteForce);
document.getElementById('btnReset').addEventListener('click', reset);
render();
Result
Console

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(nlog⁡n)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.

The Real Complexity

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

  • Brute force checks all 2n2^{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(n2)O(n^{2}) time and O(n)O(n) space.
  • Patience sorting (also called the patience solitaire algorithm) achieves O(nlog⁡n)O(n \log n) time. Each new number is placed with a binary search over the currently sorted pile tops — O(log⁡n)O(\log n) per element, O(n)O(n) total space.
  • Is O(nlog⁡n)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(nlog⁡n)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)O(nm) but resists sub-quadratic solutions for general alphabets.

Where It Matters

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?"

Conclusion

The longest increasing subsequence starts as a puzzle you could brute-force badly, improves with dynamic programming to O(n2)O(n^{2}), and then patience sorting delivers a beautiful O(nlog⁡n)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/longest-increasing-subsequence/Content licensed under CC BY-NC 4.0.