The Idea Behind the O(n log n) Method for Increasing Subsequences

The O(n log n) method finds the length of the longest increasing subsequence by keeping one list, tails, where tails[k] is the smallest value that can end an increasing subsequence of length k + 1, and placing each new value with a binary search. This card explains why that list stays sorted, traces it on the same eight numbers as Longest Increasing Subsequence in O(n²), and shows why its length is the answer but its contents may not be a subsequence at all.

A small tail is worth more than a large one, because more later values can extend it. So when a new value arrives, it either extends the longest run found until then, if it is larger than every tail, or it replaces the first tail that is not smaller than it, giving that run length a smaller ending. The position to replace is the lower bound of the value in tails, the first position holding a value at least as large, which Binary Search finds in O(log n) steps.

The trace below runs 5 2 8 6 3 6 9 7. The marker shows the position each value was placed at, by appending or by replacing.

The list stays sorted because a value replaces the first tail at least as large as itself, so it is still larger than the tail before it and no larger than the one it replaced. Sorted is what makes the binary search possible, and each of the n values costs one search, so the whole method is O(n log n).

The length of tails is the length of the longest increasing subsequence, 4, the same as the O(n²) method gave. Its contents are only a record of the best endings, and here 2 3 6 7 happens to be an increasing subsequence of the input. It need not be. On 3 4 1 the run ended with tails 1 4: the 1 replaced the 3 because a run of length 1 ending at 1 is the better start, but 1 comes after 4 in the input, so 1 4 is not a subsequence of it. The length, 2, is still right. Recovering an actual subsequence needs a parent array as in the O(n²) method, recording for each value the position of the tail before it.