Give the O(n log n) longest increasing subsequence algorithm and explain why the auxiliary array it maintains is generally not itself an increasing subsequence of the input. How do you recover an actual optimal subsequence?

Give the O(n log n) longest increasing subsequence algorithm and explain why the auxiliary array it maintains is generally not itself an increasing subsequence of the input. How do you recover an actual optimal subsequence?

Approach: The array holds the smallest possible tail for each achievable length. Track what each entry means at the moment it is written and what happens to it later.

O(n log n). Keep an array tails where tails[k] is the smallest value that ends an increasing subsequence of length k + 1 among the elements seen so far. For each element x, binary search for the first entry that is at least x and overwrite it, or append x when none is at least x, which is the patience sorting pile rule. Each step is O(log n) and the answer is the final length of tails. The array is not a subsequence of the input because entries written at different times can come from positions in any order: on 3, 4, 5, 1, 2 the array ends as 1, 2, 5, whose elements do not appear in that order in the input, and only the length is meaningful. To recover an optimal subsequence, store for every input element the length it achieved and predecessor pointers to the element that was at the previous position in tails when it was written, then follow the pointers back from the element that achieved the maximum length. That adds O(n) memory and leaves the time bound unchanged.

Follow-up: How does the same structure give the longest non-decreasing subsequence, and which comparison changes?

Key concepts: patience sorting, smallest tail, binary search, predecessor pointers.