Longest increasing subsequence
The cell for a position holds the length of the longest increasing subsequence that ends at that position. To work it out, look back at every earlier position; any whose number is smaller could be extended by this one, so take the best of those and add one. A position with nothing smaller before it starts a run of its own, of length one. The answer is the largest number anywhere in the row, which is not necessarily the last.
Its recurrence
L(j) = 1 + max over i < j with a[i] < a[j] of L(i)
When it is the right choice
Sorting out the longest consistent run in a sequence: patience sorting, the box-stacking and activity-chaining family of puzzles, and measuring how far a list is from being sorted. The quadratic version here is the one worth understanding first; there is an O(n log n) version that keeps a sorted list of best tails instead of a table, and it is faster and teaches less.
How it works
- Make a row of cells, one per number in the sequence.
- Write 1 into every cell to begin with: any single number is an increasing run of length one.
- For each position in turn, look back at every earlier position.
- Where the earlier number is smaller, that run can be extended: one more than its cell is a candidate.
- Keep the best candidate, and remember which position it came from.
- Walk back from the largest cell in the row, following the remembered positions, to read the subsequence off in reverse.
Worth noticing
- This is the only page here where the number of arrows grows with the input. Every other recurrence looks back at a fixed two or three cells; this one looks back at everything, which is where the second factor of n in the cost comes from and why the arrows sweep rather than point.
- A look-back at a number that is not smaller is refused, and the refusal is drawn. Most of the work on this page is refusals, which is the honest picture of a quadratic scan.
- The answer is not in the last cell. Every other page in this tool reads its answer out of one known corner; here you have to find the largest cell first, and the traceback starts from wherever that is.
Cost
- Best
- O(n²)
- Average
- O(n²)
- Worst
- O(n²)
- Extra space
- O(n)
- Table
- one dimension
- Accepts
- 2 to 20 numbers, each from 0 to 99
The limits are pedagogical rather than technical: this tool keeps the whole table in every recorded step, so the shape of the table sets the size of the trace directly, and a run has to stay short enough to sit and watch. An input that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the input sizes rather than by running it and finding out.
An unfilled cell is drawn differently from a cell holding a zero — no fill, a dashed outline, and no number at all — because early in a run that difference is most of the picture.