Longest increasing subsequence

O(n²)

The longest increasing subsequence (LIS) is the longest set of array elements, taken in their original order, whose values strictly increase — they don't have to be next to each other. The O(n²) DP keeps dp[i] = the length of the best increasing subsequence that ends exactly at index i. To fill it, each element looks back at every earlier element smaller than itself and extends that one's run, keeping the longest; a parent pointer records the choice so the actual subsequence can be traced back at the end. The answer is the largest dp value. (A cleverer O(n log n) version exists using patience sorting.) LIS shows up in diffing, box-stacking, and patience-game analysis.

Array
Edit the input and press Play

How it works

  1. Give every element a subsequence of length 1 (itself).
  2. For each element, look back at all earlier, smaller elements.
  3. Extend the longest run found among them and remember that predecessor.
  4. The largest length wins; walk the parent pointers back for the subsequence (highlighted).

Pseudocode

1lis(a):                             # O(n²)2  dp[i] ← 1 for all i               # each element alone3  for i in 0..n-1:4    for j in 0..i-1:5      if a[j] < a[i] and dp[j]+1 > dp[i]:6        dp[i] ← dp[j] + 1            # extend the best run ending at j7        parent[i] ← j8  answer ← max(dp)                   # walk parents back for the actual run