Longest Increasing Subsequence

The 10-second versionCopy Anchor Link

The longest increasing subsequence of an array is the longest run you can pick out while keeping the original order and going strictly upward — the picked items don't have to be adjacent. There's a clean O(n²) dynamic program: dp[i] is the length of the best increasing subsequence ending at index i. Then there's a beautiful O(n log n) trick called patience sorting: keep a small tails array where tails[k] is the smallest possible last element of any increasing subsequence of length k + 1, and for each new number binary-search where it belongs. The length of tails is your answer.

Why this existedCopy Anchor Link

The story starts with a theorem, not an algorithm. In 1935, Paul Erdős and George Szekeres proved something surprisingly strong: any sequence of more than (r - 1)(s - 1) distinct numbers must contain either an increasing subsequence of length r or a decreasing one of length s. To even state that bound, you have to be able to find long monotone subsequences — and so the longest increasing subsequence became an object worth computing.

In parallel there was a card game. Patience sorting is a one-player game: deal a shuffled deck left to right into piles, always placing each card on the leftmost pile whose top card is larger, and starting a new pile when no pile qualifies. It looks like pure card-shuffling — and yet the number of piles you end up with is exactly the length of the longest increasing subsequence of the deal. Combinatorialists already knew pieces of this through the Robinson–Schensted correspondence (Robinson 1938, Schensted 1961), which ties permutations, Young tableaux, and the shapes of those piles together.

The modern capstone is a 1999 paper by David Aldous and Persi Diaconis, "Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem." They showed that patience sorting is the longest-increasing-subsequence algorithm, and connected it to Ulam's problem — the average LIS length of a random permutation, which grows like 2√n and lives, astonishingly, in the same mathematics as random matrices and the longest run in a particle system.

Why it mattered then: the Erdős–Szekeres bound was one of the founding results of combinatorics, and this little sequence problem turned out to be the combinatorial skeleton underneath far bigger things — tableaux, random matrices, particle systems. Few toy problems have paid off so widely.

Inside the inventor's headCopy Anchor Link

Start naive. A subsequence keeps the original order but may skip elements, so for each element you might extend any earlier element that is smaller. Try every increasing chain recursively and you get an exponential search — each element can join or not, in every combination that stays increasing.

The first honest fix is the standard DP: let dp[i] be the length of the longest increasing subsequence ending at index i. Any such subsequence either is just a[i] by itself, or it is some increasing subsequence ending at an earlier j where a[j] is smaller, with a[i] appended. So take the best j. That's O(n²) — the version you'll write in an interview when you're not thinking hard.

function lis2(a) {  const dp = new Array(a.length).fill(1);  let best = 0;  for (let i = 0; i < a.length; i++) {    for (let j = 0; j < i; j++)      if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + 1);    best = Math.max(best, dp[i]);  }  return best;}

O(n²) is fine, and it's not wrong. But now the pivot, and it's a lovely one. Think about all the increasing subsequences you could extend later. For a fixed length, you don't care about most of them — you care about the one with the smallest possible last element, because a smaller tail is easier to extend with whatever comes next. Every other subsequence of that length is dominated and can be forgotten.

So keep a tiny array tails, where tails[k] is the smallest tail of any increasing subsequence of length k + 1. Deal the numbers in one at a time:

• if a number is larger than every tail so far, it starts a new, longer pile (append);
• otherwise it replaces the first tail that is ≥ it, because it is a better — smaller — tail for that length.

That is exactly the patience-sorting card game. Here's the deal for the sequence 9, 2, 5, 3, 7, 101, 18, where each new card lands on the leftmost pile it can top:

Four piles — so the longest increasing subsequence has length 4 (for example 2, 3, 7, 101). The number of piles is the answer, and the aha is that we never once stored an actual subsequence.

The final approachCopy Anchor Link

The two algorithmsCopy Anchor Link

The O(n²) DP, precisely: dp[i] = 1 + max{ dp[j] : j < i and a[j] < a[i] }, with 1 when no such j exists. The answer is max(dp).

The O(n log n) patience method, precisely: maintain tails, and for each x find the leftmost index whose value is ≥ x (a lower bound) and set tails[index] = x. If that index is past the end, append instead. Both steps are a single binary search plus a write:

The invariantCopy Anchor Link

tails is always sorted non-decreasing, and tails[k] equals the smallest possible last element among all increasing subsequences of length k + 1. That's what makes the binary search valid and why appending means "I just found a longer subsequence than any before." Careful: tails is not the subsequence itself — only its length is the answer. A common trap is to print tails as the LIS, which is wrong on inputs like 9, 2, 5, 3, 7, 101, 18.

A worked traceCopy Anchor Link

Deal 9, 2, 5, 3, 7, 101, 18 and watch tails grow and shrink in value:

The final length is 4. Every step is one binary search over a sorted array, so n steps cost O(n log n).

Here's the fast version in full. In each language you'll see a lower-bound search followed by a write — the whole algorithm:

function lis(a) {  const tails = [];                              // tails[k] = smallest tail of length k+1  for (const x of a) {    let lo = 0, hi = tails.length;    while (lo < hi) {                            // lower_bound      const mid = (lo + hi) >> 1;      if (tails[mid] < x) lo = mid + 1;      else hi = mid;    }    tails[lo] = x;                               // replace, or append past the end  }  return tails.length;}

ComplexityCopy Anchor Link

The quadratic DP always does the full triangle of comparisons, so every case is Θ(n²). The patience method is Θ(n log n) in every case too — even an already-sorted input does its n binary searches — with the only best-case anecdote being that on random data each search is over a small tails, which hides the log factor in practice.

Where you meet it todayCopy Anchor Link

• Longest chains of pairs. "Russian doll" envelopes, scheduling jobs by profit, or boxing rules all reduce to: sort by one key, then take the LIS of the other. The O(n log n) version is why these scale to millions of rows.
• Version control and diff. Some diffs of similar files determine the longest matching run with LIS over matched line positions — a shared subsequence of both files.
• Patience and card software. The piles really are the algorithm; patience-sorting implementations sort decks and, as a free by-product, report the LIS length.
• Ulam's problem and random permutations. The expected LIS of a random shuffle — 2√n — is a doorway into random matrix theory; the exact same tails array is the first line of many of those papers.

Here's the chain-of-pairs use — sort by the first coordinate ascending and the second descending, then run the tails LIS on the second coordinate:

function longestChain(pairs) {  const s = [...pairs].sort((x, y) => x[0] - y[0] || y[1] - x[1]);  const tails = [];  for (const [, b] of s) {    let lo = 0, hi = tails.length;    while (lo < hi) {      const mid = (lo + hi) >> 1;      if (tails[mid] < b) lo = mid + 1;      else hi = mid;    }    tails[lo] = b;  }  return tails.length;}

RecapCopy Anchor Link

• LIS keeps the original order but may skip elements; it need not be contiguous.
• The O(n²) DP is dp[i] = 1 + max{ dp[j] : j < i, a[j] < a[i] } — short and obvious.
• The O(n log n) trick keeps only the smallest tail per length in a tails array and binary-searches each new value into place; its length is the answer.
• tails is not the subsequence. Only its size is meaningful.
• That card game — patience sorting — is the same algorithm, and the Robinson–Schensted correspondence is why piles are Young tableaux in disguise.

Next up: Bit Manipulation & Bitmask DP — where a whole subset fits in one integer and opens up a new kind of state.