After the O(n log n) longest-increasing-subsequence scan, what does the tails array actually contain?

## The invariant The fast method for the longest increasing subsequence maintains one auxiliary array. Its meaning is precise, and stating it is most of the answer: > `tails[k]` = the **smallest value** that can end a strictly increasing subsequence of length `k+1`, among everything seen so far. Two consequences follow. `tails` is sorted ascending, because a subsequence of length `k+1` ends on a value that some length-`k` subsequence could be extended past. And `tails` never shrinks: each incoming value either exceeds every entry and appends one — the only step that increases the answer — or replaces the first entry that is not smaller than it, lowering a tail without changing any length. Each step does a logarithmic search over the sorted array, giving O(n log n) time and O(n) space. Greedy intuition: keeping every achievable length ending as low as possible maximizes the chance that a future value can extend it, and lowering a tail never costs you a length you already had. ## Why the contents are not the answer The misconception is natural — the array is sorted, increasing and exactly the right length, so it *looks* like the subsequence. It is not, and the reason is that entries are written at different times from different positions in the input, with no requirement that a later-written entry sit later in the input. Trace the daily counts `2, 6, 8, 3, 4, 5, 1`: | day | count | action | tails after | |-----|-------|--------|-------------| | 0 | 2 | append | 2 | | 1 | 6 | append | 2, 6 | | 2 | 8 | append | 2, 6, 8 | | 3 | 3 | replaces 6 | 2, 3, 8 | | 4 | 4 | replaces 8 | 2, 3, 4 | | 5 | 5 | append | 2, 3, 4, 5 | | 6 | 1 | replaces 2 | 1, 3, 4, 5 | The final length, 4, is correct: `2, 3, 4, 5` is a longest increasing subsequence. But the final contents are `1, 3, 4, 5`, and the 1 arrived on the **last** day. There is no way to read `1, 3, 4, 5` off the input in order — it is not a subsequence at all. Reporting it as "the days when engagement climbed" would name a day that comes after every other day in the chain. A weaker but equally wrong version of the same claim: "the intermediate `tails` snapshots are subsequences." They are not guaranteed to be either; only the length is meaningful, at every step. ## Reconstructing the real subsequence The repair is cheap and worth knowing, because in practice you are usually asked *which* days, not merely how many. 1. When element `i` is placed at position `k` of `tails`, store `lengthAt[i] = k + 1`. 2. Store `parent[i] =` the index of the element currently occupying `tails` position `k - 1` (undefined when `k = 0`). This requires keeping, alongside `tails`, the input index of whichever element last wrote each position. 3. After the scan, take the element with the largest `lengthAt`, and follow `parent` links back. Reverse the collected indices. Why this is correct: at the moment element `i` lands at position `k`, the element then holding position `k-1` was seen earlier in the input and holds a smaller value, so it is a legal predecessor. Later overwrites of position `k-1` cannot invalidate the link already captured, because the link records a specific element, not a slot. That distinction — snapshot the element, not the slot — is the whole trick, and it is exactly the confusion behind "the tails array is the subsequence". Cost: O(n) extra space for the two arrays, no change to the O(n log n) time. ## Ties, strictness, and what breaks Strictly increasing versus non-decreasing is decided by which boundary the search uses when the incoming value equals an entry: replacing the first entry *not smaller* than the value gives the strict version; replacing the first entry *strictly greater* gives the non-decreasing one. Getting this backwards is silent — the length is off by one only on inputs with duplicates, which is precisely the case that plateau-heavy real data hits and hand-picked test data misses. ## When to reach for it at all The quadratic dynamic program, with one state per index recording the best subsequence ending there, is slower but far easier to modify and to reconstruct from — its parent pointers are the argmax you already computed. The fast method wins when n makes the quadratic version untenable and the requirement is a length or a length plus a single reconstruction. If the metric's definition is still moving — weights, custom comparisons, reporting all optimal chains — the quadratic formulation absorbs those changes and the tails formulation resists them. Choose deliberately, and if you choose the fast one, write down the invariant above in a comment: it is the piece the next reader will otherwise guess at, usually wrongly.