Cairn

algorithms · dynamic programming · O(n log n)

↩ back to Dynamic Programming

Longest Increasing Subsequence

The site's fourth dynamic programming entry, and a fresh pick with a hook the other three don't have: its fastest known approach isn't really a DP recurrence at all, it's binary search wearing a different hat. Given a sequence of numbers, find the length of the longest subsequence — elements kept in their original order, but not necessarily contiguous — that's strictly increasing. On [10, 9, 2, 5, 3, 7, 101, 18], one answer is [2, 3, 7, 18], length 4. There's a straightforward O(n²) table for this, built the same way Longest Common Subsequence and Edit Distance build theirs — and a genuinely different O(n log n) approach that this page's demo uses, built on a card-sorting trick called patience sorting.

Try it

The classic textbook example, [10, 9, 2, 5, 3, 7, 101, 18], not user-editable — same fixed-content convention as this site's other interactive demos. Press Step or Run to scan the array left to right. For each element, the demo binary-searches a second array — tails — reusing exactly the lo/hi/mid narrowing Binary Search's own demo steps through, just searching for a boundary instead of an exact match. Once the scan finishes, it backtracks through saved predecessor pointers to recover an actual longest increasing subsequence, highlighted in the top row.

Why it works

The straightforward version defines dp[i] as the length of the longest increasing subsequence that ends exactly at index i — not "within the first i elements," a subtly different definition that would break the recurrence below, since it wouldn't say anything about whether index i itself is usable as the end of a chain. dp[i] starts at 1 (every element is a valid length-one subsequence on its own), then checks every earlier index j < i: if arr[j] < arr[i], the run ending at j can be extended by arr[i], giving a candidate length dp[j] + 1. Take the best candidate over all valid j, remembering which one it came from:

dp[i] = 1 + max(dp[j] for all j < i where arr[j] < arr[i])   (or 1, if no such j exists)

The answer for the whole array is the largest value anywhere in dp, not necessarily dp[n-1] — the longest run doesn't have to end at the last element. On the demo array, this table looks like:

The largest value in dp is 4, first reached at index 6 (value 101) and reached again at index 7 (value 18) — two different indices tie for the longest run, a point the Pitfalls section below returns to.

Reference implementation (O(n²))

function lis(arr) {
  const n = arr.length;
  const dp = new Array(n).fill(1);
  const pred = new Array(n).fill(-1);

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
        pred[i] = j;
      }
    }
  }

  let bestLen = 0, bestIdx = -1;
  for (let i = 0; i < n; i++) {
    if (dp[i] > bestLen) { bestLen = dp[i]; bestIdx = i; }
  }

  const seq = [];
  for (let i = bestIdx; i !== -1; i = pred[i]) seq.push(arr[i]);
  seq.reverse();

  return { length: bestLen, seq };
}

Faster: O(n log n) with binary search

The O(n²) table re-derives, for every index i, "what's the best run length reachable so far" by rescanning everything before it. Patience sorting — named after the solitaire card game it comes from — keeps that information around instead of rebuilding it, in an array called tails. tails[k] holds the smallest value that any increasing subsequence of length k + 1 found so far can end on. Smallest is the whole trick: the smaller a run's ending value, the easier it is to extend later, so tails only ever needs to remember the best (smallest) ending value per length, never every run that achieves it.

For each new element x, tails is always sorted (a short exercise in the invariant confirms this), so finding where x belongs is exactly a binary search: find the leftmost position whose value is >= x. If one exists, x is a tighter (smaller-or-equal) ending value for that length — replace it. If none exists, x extends the longest run found so far — append it, growing tails by one. Either way, only tails's length is guaranteed meaningful at any given moment; reconstructing the actual sequence needs a separate pred array recorded alongside it, the same idea as the O(n²) version above, just populated during the binary search instead of a full rescan.

function lisFast(arr) {
  const n = arr.length;
  const tails = []; // indices into arr
  const pred = new Array(n).fill(-1);

  for (let i = 0; i < n; i++) {
    const x = arr[i];
    let lo = 0, hi = tails.length;
    while (lo < hi) {                     // binary search: leftmost tail >= x
      const mid = (lo + hi) >> 1;
      if (arr[tails[mid]] >= x) hi = mid;
      else lo = mid + 1;
    }
    if (lo > 0) pred[i] = tails[lo - 1];
    if (lo === tails.length) tails.push(i);
    else tails[lo] = i;
  }

  const seq = [];
  for (let i = tails.length ? tails[tails.length - 1] : -1; i !== -1; i = pred[i]) seq.push(arr[i]);
  seq.reverse();

  return { length: tails.length, seq };
}

Each of the n elements does one O(log n) binary search into an array that never holds more than n entries — O(n log n) total, down from O(n²). Note the search condition, arr[tails[mid]] >= x, looks for a boundary rather than an exact match: it always narrows to a single answer without ever needing a "not found" case, unlike Binary Search's canonical form, which stops early on a match or gives up when lo passes hi. Same halving idea, applied to a slightly different question.

Pitfalls

The final tails array is not itself a valid subsequence of the input — a common misreading of what it means. It's tempting to just read tails's values off at the end and call that the answer, but each slot gets overwritten independently as tighter values are found, so the values that end up sitting next to each other in tails may never have co-occurred, in that order, in the original array. Concretely, on [4, 5, 10, 0, 10, 11]: tails ends up holding indices [3, 1, 4, 5], i.e. values [0, 5, 10, 11] — but index 1 (the 5) comes before index 3 (the 0) in the array, so "0 then 5" was never actually achievable in that order. The real answer, recovered by following pred pointers from tails's last entry rather than reading tails directly, is [4, 5, 10, 11] (indices [0, 1, 4, 5]) — same length, a genuinely different and actually valid sequence.

"Increasing" means strictly increasing here — equal adjacent values don't extend a run. Change every < to <= (and the binary search's >= to >) to answer the different question of longest non-decreasing subsequence, where ties do extend a run. The two questions give different answers whenever the input has duplicates: on [1, 3, 3, 4], the strict version returns length 3 ([1, 3, 4], only one of the two 3s usable), while the non-decreasing version returns 4 (all of it). On [3, 3, 3] the gap is starker still — strict gives 1, non-decreasing gives 3. Whichever variant a problem calls for, get the comparison direction right in both places (the recurrence or binary search condition, and its mirror), not just one.

Two correct algorithms — even two runs of the same algorithm with a different tie-break — can recover different, equally valid longest subsequences from identical input. This page's own demo array proves it three ways: the O(n²) table above, breaking ties toward the first index that reaches the max length, recovers [2, 5, 7, 101]; the same table breaking ties toward the last index recovers [2, 5, 7, 18]; and the O(n log n) patience-sorting approach the live demo runs recovers [2, 3, 7, 18]. All three have length 4, all three are genuinely valid increasing subsequences of the input — none is more "correct" than the others. Only the length is ever unambiguous; which specific sequence gets reported depends on implementation details, the same caveat Knapsack and Longest Common Subsequence already raise about their own backtracking ties.

Complexity

Time: O(n²) for the direct DP table (one comparison per pair i, j), or O(n log n) for patience sorting (one binary search per element). Space: O(n) for either approach — the DP table only needs one value per index, not a 2D grid like Longest Common Subsequence or Edit Distance, since dp[i] only ever depends on entries before it in the same array.

The pattern behind patience sorting — keep only the best (smallest, in this case) representative per bucket instead of every candidate, and binary-search for where a new item belongs — shows up under different names anywhere a "longest chain of compatible things" question can be reduced to a single sorted array: stacking boxes where each must be strictly larger than the one below, version-upgrade chains where each step must strictly improve on the last, or (the trick's namesake) figuring out the minimum number of patience/solitaire piles a shuffled deck can be sorted into.

This site's guide, Choosing a Dynamic Programming Approach, compares this entry against the other ten Dynamic Programming entries side by side.