- Being filled
- Read from
- Answer
Longest increasing subsequence (LIS)
In a list of numbers, how many can you pick, keeping their order, so that each one is bigger than the last? The longest increasing subsequence answers that. Type a list and watch dynamic programming work out, for every position, the longest run that ends there. Press Play to watch the table fill, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. Type a list of numbers. For each position the table holds the length of the longest increasing run of values that ends there, and the earlier position it continues. Tick Allow equal values for runs that never go down. At the end the run is read back from its last value. New example makes another list. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Type a list of numbers, separated by commas or spaces. Tick Allow equal values for runs that never go down.
- Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere.
- Watch each position compared with every earlier one, then see the longest run read back in orange.
How the table works
The table has three rows: the values, the length of the longest increasing subsequence that ends at each position, and the position it continues. A value on its own is a run of length 1. Then every earlier position is checked: if its value is smaller, the run that ends there can be extended by this value, giving one more than its length. The longest such extension wins, and its position goes in the third row.
Reading back the run
The longest increasing subsequence ends at the position with the biggest length. From there, the third row says which position comes before it, and that position's third row says which comes before that, until a position with no predecessor. Read in order, those values are the answer. With Allow equal values ticked, a value may also follow an equal one, which gives the longest run that never goes down.
Frequently asked questions
What is the difference between a subsequence and a subarray?
A subarray is a block of neighbouring values. A subsequence keeps the order but may skip values, so in 3, 10, 2, 1, 20 the values 3, 10 and 20 form an increasing subsequence even though 2 and 1 sit between them.
How fast is the LIS algorithm?
The table method compares every pair of positions: n·(n − 1)/2 comparisons for n values. Patience sorting does it in O(n log n): it keeps, for every length, the smallest value that ends a run of that length, and places each new value by binary search.
Is the longest increasing subsequence unique?
Not always. In 1, 3, 2, 4 both 1, 3, 4 and 1, 2, 4 have length 3. The table gives the length, and the read-back finds one of them.
Where is the longest increasing subsequence used?
In comparing files and genomes, where some methods first find matching lines and then take an increasing subsequence of their positions; in scheduling and box-stacking puzzles; and in mathematics, where the length of the LIS of a random shuffle is a famous object of study.
Is anything sent anywhere?
No. Everything is worked out in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor