= Pile top in patience sorting
A <pile top in patience sorting> is the currently exposed value on one pile. With the rule “place the next value $x$ on the leftmost pile whose top is at least $x$,” pile tops remain strictly increasing from left to right. Replacing the chosen top preserves that invariant: all earlier tops are smaller than $x$, and later tops exceed the old chosen top and hence $x$.
More strongly, top $i$ is the smallest possible last value of an <increasing subsequence> of length $i+1$ among the entries seen so far. A smaller last value leaves more options for extending that <subsequence>. For `3,1,2`, the top arrays are `[3]`, `[1]`, `[1,2]`. <binary search> finds each replacement position in logarithmic time. The final top array gives the length but need not itself be a <subsequence>: `2,3,1` ends with tops `[1,3]`, although1 appeared after3. Predecessor pointers are needed to reconstruct a witness.
Back to article page
