Longest Increasing Subsequence: O(n^2) and O(n log n) Patience

What This Concept Is

A strictly increasing subsequence preserves input index order and has strictly increasing values. It need not be contiguous. For nonempty input define L(i) as the longest such subsequence ending at i:

L(i)=1+max({L(j): j<i and a[j]<a[i]} union {0}).

The last predecessor partitions the possibilities. O(n²) comparisons compute all states; predecessors recover a witness. Empty input has length 0, avoiding an undefined maximum over no endpoints.

The faster algorithm stores tails[k]: the smallest endpoint value achievable by a subsequence of length k+1 in the processed prefix. For a new x, find the first tail at least x using lower-bound search, then replace it or append x.

Why It Matters Here

This is a dominance reduction. For the same length, a smaller ending value can be extended by every future value that could extend a larger ending value. The discarded state cannot improve the optimal length later. Explain this dominance before claiming a smaller array is sufficient. Witness reconstruction needs information beyond the minimum tail values themselves.

Concrete Examples

For [3,5,6,2,4], tails evolve [3], [3,5], [3,5,6], [2,5,6], [2,4,6]. Length is 3 and indices [0,1,2] provide [3,5,6]. The final tails array is not a valid subsequence: its 6 occurs before 2 and 4.

Why the update works. If x replaces position k, the preceding tail is less than x, so an existing length-k sequence can extend to length k+1. Positions before k already have smaller tails. Positions after k require longer sequences; x cannot create one because no length-(k+1) tail is less than x. Replacing with a smaller/equal endpoint preserves possible future extensions. These facts also keep tails strictly increasing, licensing binary search.

Duplicates. Input [2,2,2] has strict LIS length 1. First-tail->=x replaces position 0 each time. Searching first-tail->x instead computes a longest nondecreasing subsequence, whose length here is 3. This is a semantic change, not a harmless tie policy.

For reconstruction, keep the input index at each tail position and set prev[i] to the endpoint index at position k-1 before the replacement. Follow predecessors from the final longest endpoint and reverse the indices. All predecessors have smaller indices, so the chain terminates and respects order.

Common Confusion / Misconceptions

Sorting the input destroys the original order constraint. A subsequence is not a substring. Patience-pile descriptions must specify equality behavior: for strict LIS, place on the first pile with top at least the new value. O(n log(n+1)) is the total comparison bound; each binary search takes O(log(n+1)), not O(n log n) per element. Reconstruction adds O(n) storage and O(n) worst-case work.

How To Use It

Implement the quadratic recurrence first as a learning exercise, then justify tails dominance. In the lab, return original indices. Check increasing indices, strict values and length equality separately. Enumerate all subsequences on tiny inputs; include duplicates, decreasing input, negative values and empty input. Do not require the reference's particular tied subsequence.

Check Yourself

Why can replacing a tail help without increasing the current length? Why are tails not necessarily a witness? What would change for nondecreasing output?

Mini Drill or Application

For [2,2,1,3], give strict and nondecreasing answers with indices. Feedback: strict length 2, for example [0,3]; nondecreasing length 3, [0,1,3]. State the exact inequality used by both search variants.

Read This Only If Stuck

Skiena: longest increasing sequence. Reconstruct the quadratic proof before using the faster implementation in Lab A.