The idea: the longest run that keeps going up
A subsequence keeps the order of a sequence but may skip elements. The longest increasing subsequence (LIS) is the longest one whose values go strictly up. In 10 9 2 5 3 7 101 18 it has length 4, and there is more than one: 2 5 7 101 and 2 3 7 18 both work. The page finds it two ways on the same input: a dynamic programming table that compares every pair, O(n²), and patience sorting, which deals the numbers onto piles and uses binary search, O(n log n).
The O(n²) DP
Let L[i] be the length of the longest increasing subsequence that ends at a[i]. Such a subsequence is a[i] alone, or a shorter one ending at some earlier a[j] < a[i], with a[i] added:
L[i] = 1 + max { L[j] : j < i and a[j] < a[i] }, or 1 when no such j exists.
The page fills L from left to right. For each i it compares a[i] with every earlier a[j] (blue) and keeps the best, and prev[i] remembers which j gave it. The LIS ends at the largest L[i]; following prev[] back gives the whole sequence in reverse. Every pair (j, i) is compared once, so the work is n(n−1)/2 comparisons: 28 for 8 numbers, 66 for 12. (Demo: O(n²) DP on 10 9 2 5 3 7 101 18)
Patience sorting
Deal the numbers like cards, left to right. Each card goes on the leftmost pile whose top card is ≥ it; if there is none, it starts a new pile on the right. At the end, the number of piles is the length of the LIS. Cards on one pile go down (each is ≤ the one under it), so an increasing subsequence uses at most one card per pile; and the back-pointers below build one that uses every pile.
Keep the top cards in an array tails. tails[k] is the smallest possible last value of an increasing subsequence of length k + 1 seen so far. A new card only ever replaces a top by a smaller value or adds a bigger one at the end, so tails stays sorted. That is why the right pile can be found by binary search: lo = 0, hi = number of piles, look at tails[mid], and halve the range. Each card costs about log₂(piles) probes, so n cards cost O(n log n). (Demo: patience sorting on the same input; Demo: both on 12 digits of π, 66 comparisons against 20 probes)
Strictly increasing: lower bound
The search looks for the first top that is ≥ the card (a lower bound). So an equal card lands on the same pile, on top of its twin, and can never extend a subsequence that ends in the same value. For a non-decreasing subsequence, search for the first top that is > the card instead (an upper bound). (Demo: equal values 3 5 5 2 5 7: the three 5s share pile 1, and the LIS is 2 5 7, length 3.) A falling input puts every card on pile 0: one pile, LIS length 1. (Demo: falling input)
Rebuilding the sequence
The length alone is not enough; we want the numbers. When a card is placed on pile k, it stores a back-pointer to the card that is on top of pile k − 1 at that moment. That card came earlier and is smaller, so the pointers always form an increasing subsequence. Start at the top of the last pile and follow them to pile 0.
Do not read the answer off tails. For 2 5 3 7 4 1, tails ends as 1 3 4, but 1 comes last in the input, so 1 3 4 is not a subsequence at all. The back-pointers give 2 3 4. (Demo: the tails array is not the LIS) Real code keeps only two index arrays: the index on top of each pile, and the back-pointer of each element.
The two methods side by side
| O(n²) DP | patience sorting | |
|---|---|---|
| state | L[i] and prev[i] for every i | tails (one top per pile) and a back-pointer per card |
| work per element | compare with all earlier elements | binary search over the piles |
| total | n(n−1)/2 comparisons, O(n²) | O(n log n) probes |
| 10 9 2 5 3 7 101 18 | 28 comparisons → 2 5 7 101 | 10 probes → 2 3 7 18 |
| 3 1 4 1 5 9 2 6 5 3 5 8 | 66 comparisons → 3 4 5 6 8 | 20 probes → 1 2 3 5 8 |
| good for | small n, or variants (longest chain with any rule, weighted LIS) | large n: 10⁵ numbers in about 2 million steps |
The DP is easy to change: replace "a[j] < a[i]" by any rule (boxes that fit inside each other, pairs sorted by two keys) and it still works. Patience sorting needs the "less than" of plain numbers to keep tails sorted.
See also Longest Common Subsequence: the LIS of a sequence is the LCS of the sequence and its sorted copy without duplicates, an O(n²) route to the same answer. The binary search is the one on Linear, Binary and Interpolation Search, and 0/1 Knapsack uses the same fill-a-table, then-trace-back pattern.
What the page leaves out
Inputs are capped at 12 numbers so both panels fit. The page leaves out the weighted LIS (a Fenwick tree or segment tree over values), counting how many LIS there are, the longest decreasing or bitonic subsequence, Dilworth's theorem (the minimum number of decreasing sequences that cover the input equals the LIS length), the 2D "Russian doll envelopes" variant, and the link between patience sorting, Young tableaux and the expected LIS length of about 2√n for a random permutation.