Longest Increasing Subsequence and the Tails Array Invariant

The longest increasing subsequence problem takes a sequence of n numbers and asks for the length of the longest subsequence whose values strictly increase, with indices in order. The direct DP is dp[i] = 1 + max{ dp[j] : j < i and a[j] < a[i] }, which is Θ(n²) because each of the n cells scans up to i predecessors. The patience-sorting method computes the same length in Θ(n log n) by discarding almost all of that table. What survives is a single array holding, for each achievable length, the smallest value that can end a subsequence of that length.

That array is not the answer and does not contain the answer. Understanding why it can replace the table, and where the replacement breaks down, is the point.

The invariant

Let tails[ℓ] be the minimum possible last element of an increasing subsequence of length ℓ + 1 using the prefix processed so far. The array is indexed from zero, so tails[0] is the smallest element seen, tails[1] is the smallest possible second-and-final element of a two-element increasing pair, and so on.

Two properties hold at every prefix, and they are what make the array usable.

Sortedness. tails is strictly increasing. Suppose tails[ℓ] ≥ tails[ℓ+1]. A subsequence of length ℓ+2 ends at tails[ℓ+1], and its prefix of length ℓ+1 ends at some value smaller than tails[ℓ+1], hence smaller than tails[ℓ]. That contradicts the minimality of tails[ℓ]. So tails is sorted, which is what permits binary search.

Sufficiency. The length of the longest increasing subsequence of the prefix is exactly len(tails). A subsequence of length L exists if and only if tails[L-1] is defined, because tails is defined by extending subsequences and every extension corresponds to a real subsequence.

Neither property says tails is itself a longest increasing subsequence, and reading it as one is a common error. Its entries are written at different times from different positions, so their values are sorted but their positions are not. On the input 2, 3, 1, 4 the array ends as [1, 3, 4], yet the 1 occurs after the 3 and cannot follow it; 1, 3, 4 is not a subsequence of that input. The length is right — three — but the array is not a witness, which is why reconstruction needs the parent pointers described below.

The update rule

For each element x, find the first index whose value is ≥ x and replace it with x; if no such index exists, append.

from bisect import bisect_left

def lis_length(seq):
    tails = []
    for x in seq:
        i = bisect_left(tails, x)   # first entry >= x
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Replacing tails[i] with x is safe because x is at least as good an ending value as the value it replaces: any subsequence that could be extended from the old value can also be extended from x, since x ≤ old, and x occurs no earlier. This is the dominance argument. It is the same argument that licenses pruning in state sufficiency, restricted to a single scalar per length.

bisect_left versus bisect_right is the difference between the strictly increasing and the non-decreasing problem. For strict increase, x may not extend a subsequence ending in x, so the replacement target is the first entry ≥ x, which is bisect_left. For non-decreasing, a run of equal values counts, so x may extend an entry equal to it and the target is the first entry > x, which is bisect_right. Choosing wrongly changes the answer on any input with a duplicate, and the failure is silent.

Why this is patience sorting

The procedure is the card game: deal each element onto the leftmost pile whose top is at least as large, or start a new pile. The number of piles at the end equals the LIS length. The classic proof of that equality uses two bounds.

The first is that no increasing subsequence can take two cards from the same pile, because within a pile the tops decrease over time — each card placed on a pile is smaller than or equal to the card it covered — while indices increase, so any two cards in a pile are in decreasing value order. Hence the LIS length is at most the number of piles.

The second is a stronger statement about each card rather than about the final pile tops: the pile a card lands on equals the length of the longest increasing subsequence ending at that card. Induct on the input. When card x is placed on pile k, it was placed there because the current top of pile k-1 was strictly less than x — pile k-1 is to the left, so its top is smaller — and that top occurred earlier in the input. By the induction hypothesis there is an increasing subsequence of length k-1 ending at that top card, so appending x gives one of length k ending at x. Every card on pile k therefore certifies an increasing subsequence of length k, and the number of piles is at most the LIS length.

The two bounds meet. The tails array is exactly the array of pile tops, and bisect_left is the rule for choosing the pile.

The same invariant as Dilworth

The pile argument generalizes. A sequence of length n with no increasing subsequence of length k+1 can be partitioned into k non-increasing subsequences — assign each element to a pile, and each pile is non-increasing. That is the easy direction of Dilworth’s theorem for the divisibility-like order on positions and values, and it gives the Erdős–Szekeres bound: a sequence of (r-1)(s-1) + 1 distinct numbers contains an increasing subsequence of length r or a decreasing one of length s. For r = s = 5, any 17 distinct numbers contain a monotone subsequence of length 5.

The algorithmic consequence is that the LIS length is also the minimum number of non-increasing subsequences needed to cover the input. This equality is occasionally useful directly: a scheduling problem whose constraint is “no two jobs in the same chain may increase” reduces to counting piles.

Recovering the subsequence

The tails array alone cannot reconstruct a witness. Reconstruction needs, for each element, the index of the element that preceded it in the best subsequence ending there, plus the length of that subsequence. Both are computed during the same sweep:

from bisect import bisect_left

def lis_witness(seq):
    tails, tail_idx = [], []      # tails[l] and the input index holding it
    prev = [-1] * len(seq)
    length = [1] * len(seq)
    for i, x in enumerate(seq):
        l = bisect_left(tails, x)
        if l > 0:
            prev[i] = tail_idx[l - 1]
            length[i] = l + 1
        if l == len(tails):
            tails.append(x)
            tail_idx.append(i)
        else:
            tails[l] = x
            tail_idx[l] = i
    best = max(range(len(seq)), key=length.__getitem__, default=-1)
    out = []
    while best != -1:
        out.append(seq[best])
        best = prev[best]
    return out[::-1]

The prev pointer is taken before the replacement, so it points at the element that was the pile top at the time — which is a real earlier element with a smaller value. Overwriting tail_idx[l] afterwards does not invalidate pointers already recorded, because each recorded pointer refers to an index that was valid at its own moment. This is the standard forward-DP-with-parents pattern, and it costs O(n) extra space rather than the O(n²) of a full table.

The witness recovered this way is a longest increasing subsequence but not necessarily the lexicographically smallest or the one a leftmost-greedy scan would find. Any of them is acceptable for a length claim; applications that need a canonical witness must define the tie-break and implement it explicitly.

Counting, and why the array is not enough

Counting the number of longest increasing subsequences needs more than the tails array, because the array keeps one representative per length and no multiplicity. The count is still obtainable in O(n log n) with a different structure: a Fenwick tree indexed by value, where each node stores the best length achieved so far and the number of subsequences attaining it. Querying the prefix below x returns the best length ending at a smaller value and how many ways it is achieved; the count at i is that number, and the tree is updated at x with (length + 1, count). Merging two tree entries means keeping the larger length and summing counts on a tie.

The tails array cannot support this because it discards exactly the multiplicity information. It is the Pareto frontier of (value, length) pairs for the processed prefix, one point per length, and questions about how many subsequences achieve each length or about the distribution of lengths need the full set of non-dominated pairs. That set can be quadratic in size even when the frontier is linear, which is the same distinction drawn in state sufficiency between a sufficient state and a state that has thrown away what a later query needs.

Variants and their state changes

Each variant is a change of what “increasing” means, and each changes the comparison, not the algorithm.

Longest decreasing reverses the comparison: the target index is the first entry ≤ x. Alternatively negate the input and run the increasing version.

Longest bitonic (increase then decrease) runs one pass forward and one backward and combines up[i] + down[i] - 1, where up[i] is the LIS length ending at i and down[i] the longest decreasing-subsequence length starting at i. The combination is correct because the peak element is counted in both passes.

Longest increasing subsequence of a 2D partial order — points (x, y) with both coordinates increasing — sorts by x and runs the 1D algorithm on y, with the tie-break on x chosen to prevent two points with equal x from chaining. Sorting ascending on x and using strict increase on y breaks the ties incorrectly for duplicates; the repair is to sort by x ascending and y descending before the sweep, so equal-x points cannot extend one another.

Maximum sum increasing subsequence does not admit the tails trick. The objective is a sum, and two subsequences of the same length ending at the same value can have different sums; the dominance argument fails because the smaller ending value no longer implies a better state. The O(n²) DP is the standard solution, which is a useful reminder that the tails array works because of a specific dominance relation and not because “LIS is special”.

Cost and constants

Θ(n log n) comparisons and Θ(n) space, with the binary search being the only nontrivial step. For n = 10^6 the array holds a million entries at most — 4 MB as 32-bit integers — and the sweep performs about 20 million comparisons, each probing an array whose later positions were written long after the earlier ones, so the probe sequence bears little relation to the access order of the input. The O(n²) version at the same size would perform on the order of 5×10^11 comparisons, a factor of roughly 10^5 more.

The practical caveat is that bisect_left on a Python list is a C-level loop, so the per-element cost is dominated by the interpreter overhead of the outer loop rather than the search. In compiled languages the search dominates, and the branch prediction behaviour of binary search — poor, because each comparison is unpredictable — means the theoretical log n understates the cost relative to a linear scan for small n. For arrays shorter than a few dozen elements, a linear scan for the insertion point is often faster than a binary search, which is why some implementations special-case the small case.