Longest increasing subsequence (LIS)

Pick numbers from a list, from left to right, each bigger than the one before. How long can such a chain get? The question is simple enough for a puzzle book, and its answer connects a card game, a classic dynamic programming table, and one of the most beautiful results about random shuffles.

A row of bars of different heights with a rising chain of them picked out in orange, from left to right
A row of bars of different heights with a rising chain of them picked out in orange, from left to right

The problem

Given a list of numbers, a subsequence keeps some of them in their original order. It is increasing if each value is bigger than the one before. The longest increasing subsequence, or LIS, is the longest such pick. A list of n values has 2ⁿ subsequences, so checking them all only works for very short lists.

The table

Let len[i] be the length of the longest increasing subsequence that ends exactly at position i. It is 1 for the value alone, or 1 + len[j] for an earlier position j whose value is smaller, whichever is largest. Each position looks back at all earlier ones, so the table needs n·(n − 1)/2 comparisons. The answer is the largest len[i], and noting which j gave each len[i] lets you read the subsequence back.

An example

Take 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Position by position the lengths are 1, 2, 1, 1, 3, 2, 3, 4, 3 and 5: the 20 extends 3, 10; the 4 extends the 3; the 6 extends the 4, the 7 the 6, and the 9 the 7. Reading back from the 9 gives 3, 4, 6, 7, 9, an increasing subsequence of length 5.

A faster way: patience sorting

Deal the values like cards onto piles: each value goes on the leftmost pile whose top is not smaller than it, or starts a new pile on the right. The number of piles is the length of the LIS. Because the tops of the piles are always sorted, the right pile can be found by binary search, so the whole method takes O(n log n) steps. It is named after the solitaire game it resembles.

Some mathematics

In 1935 Paul Erdős and George Szekeres proved that any list of n² + 1 different numbers has an increasing or a decreasing subsequence of length n + 1. Stanislaw Ulam asked in 1961 how long the LIS of a random shuffle of n numbers is. The answer, close to 2√n for large n, was settled in 1977 by Anatoly Vershik and Sergei Kerov and by Ben Logan and Larry Shepp, and in 1999 Jinho Baik, Percy Deift and Kurt Johansson found the exact shape of its fluctuations: the Tracy–Widom distribution from random matrix theory.

Paul Erdős at a student seminar in Budapest in 1992. In 1935 he and George Szekeres proved that any list of n² + 1 different numbers has an increasing or a decreasing subsequence of length n + 1.
Paul Erdős at a student seminar in Budapest in 1992. In 1935 he and George Szekeres proved that any list of n² + 1 different numbers has an increasing or a decreasing subsequence of length n + 1.
Portrait of Stanisław Ulam
Portrait of Stanisław Ulam

Explore it

Open the app and press Step. The orange column is the position being worked out and the blue column the earlier position it is compared with. The Length row grows as longer runs are found, the Comes after row remembers where they came from, and at the end the answer is read back in orange and shown under the table.

Frequently asked questions

What is the time complexity of the LIS?

O(n²) with the table, because every position looks at every earlier one, and O(n log n) with patience sorting and binary search. Both need O(n) memory.

How do I find the longest non-decreasing subsequence?

Let a value follow an equal one: compare with ≤ instead of <. In the app, tick Allow equal values. With patience sorting, put each value on the leftmost pile whose top is strictly bigger.

What is the longest decreasing subsequence?

The same problem with the comparison turned around, or the LIS of the list with every value negated. By the Erdős–Szekeres theorem, a long enough list always has a long increasing or a long decreasing subsequence.

How long is the LIS of a random list?

For a random shuffle of n different numbers, close to 2√n for large n. The correction grows like the sixth root of n, so for a thousand numbers the average is about 58, a little under 2√1000 ≈ 63.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try the longest increasing subsequence