Longest Increasing Subsequence, in depth: the O(n^2) recurrence, the patience method in O(n log n), reconstruction and the reductions that use it

The O(n^2) dynamic program

Define dp[i] as the length of the longest increasing subsequence that ends at position i. Fixing the last element is the key move: any such subsequence is either just a[i], or some increasing subsequence ending at an earlier j with a[j] < a[i], extended by a[i]. So

dp[i] = 1 + max(dp[j] for j < i if a[j] < a[i])     # max of an empty set is 0
answer = max(dp)

Each dp[i] scans all earlier positions, so the total is O(n^2) time and O(n) space. To recover a subsequence, record the j that achieved the maximum as parent[i] and follow parents back from the position with the largest dp. The subproblem graph here is a DAG (edges go from j to i when j < i and a[j] < a[i]), and LIS is the longest path in it; the longest path in a DAG article covers that general view, and the introduction to dynamic programming covers the state-design habit used here.

The quadratic version is still worth knowing. It is the easiest to adapt (weighted LIS, or extra constraints between consecutive elements), and it is the reference you test the fast version against. It is too slow beyond a few thousand elements: on the machine used here, 5,000 elements took 0.97 seconds in Python.

The tails invariant and the O(n log n) method

The fast method keeps one array, tails, where tails[k] is the smallest value that can end an increasing subsequence of length k + 1 among the elements seen so far. Smaller tails are better, because they leave more room for future elements to extend the run.

Invariant: tails is strictly increasing. Suppose a run of length k + 2 ends in value t. Its first k + 1 elements form a run of length k + 1 ending in something smaller than t, so tails[k] < tails[k + 1]. Because tails is sorted, binary search finds where a new element x belongs:

• If x is larger than every tail, it extends the longest run: append it. The LIS length grows by one.
• Otherwise let k be the first position with tails[k] >= x. Element x extends the run of length k (whose tail tails[k - 1] is smaller than x) into a run of length k + 1 that ends in x, and x is no larger than the old tails[k]. So replace tails[k] with x. No other entry changes: x cannot end a longer run, and for shorter runs the existing tails are already smaller.

Each element costs one binary search, so the whole pass is O(n log n) time and O(L) extra space for the length, where L is the answer. The name comes from the card game: deal cards onto piles, always placing a card on the leftmost pile whose top card is not smaller, otherwise starting a new pile on the right. The pile tops are exactly tails, and the number of piles is the LIS length.

Tested code with reconstruction

Reconstruction needs more than tails. When element i lands at position k, its predecessor in the best run is whichever element currently ends a run of length k, so store the index of each tail and a parent pointer per element:

from bisect import bisect_left, bisect_right

def lis(a, strict=True):
    """Return one longest increasing subsequence of a in O(n log n)."""
    find = bisect_left if strict else bisect_right
    tails, tail_idx = [], []       # tail values and their indices in a
    parent = [-1] * len(a)
    for i, x in enumerate(a):
        k = find(tails, x)
        if k == len(tails):
            tails.append(x); tail_idx.append(i)
        else:
            tails[k] = x; tail_idx[k] = i
        parent[i] = tail_idx[k - 1] if k > 0 else -1
    out, i = [], tail_idx[-1] if tail_idx else -1
    while i != -1:
        out.append(a[i]); i = parent[i]
    return out[::-1]

The function was checked against the quadratic version on 3,000 random sequences of length 0 to 30 with many repeated values: lengths always matched, every result was increasing, and every result was a genuine subsequence of its input.

Strictness is a single character. With bisect_left, an element equal to an existing tail replaces it, so equal values never extend a run: the result is strictly increasing, and lis([5, 5, 5]) has length 1. With bisect_right, an equal value lands after its twin and extends the run, giving the longest non-decreasing subsequence, length 3 for the same input. Pick deliberately and test both cases.

Worked example: why tails is not the answer

Run the method on 3, 10, 2, 1, 20, 4, 6, 7, 5, 8. The diagram below shows tails after each element. Notice the replacements at the start: 3 is replaced by 2 and then by 1, because a run of length one ending in 1 is more useful than one ending in 3. The element 20 extends to length three, but 6 later replaces it, because the run 1, 4, 6 ends lower than 3, 10, 20 and so leaves more room.

The last step is the instructive one. Element 5 replaces 6 at position 2, then 8 extends to length 5. The final tails are 1, 4, 5, 7, 8, but that is not a subsequence of the input, because 5 appears after 7. Each entry is the best ending for its own length, recorded at different times. Following parent pointers from the element 8 gives 7, then 6 (the tail of length three when 7 arrived), then 4, then 1: the valid answer 1, 4, 6, 7, 8. The quadratic version returns a different valid answer, 3, 4, 6, 7, 8; there are three LIS in this sequence, starting from 3, 2 or 1.

Variants and reductions

Counting the LIS. Keep, for each position, the length and the number of runs ending there; when an earlier j gives a longer run, copy its count, and when it ties, add its count. That is O(n^2) as written. For large inputs, compress values to ranks and use a Fenwick tree whose nodes store the pair (best length, count) and combine by taking the larger length and adding counts on ties, for O(n log n). Counts grow exponentially, so use big integers or a modulus.

Nested envelopes. An envelope (w, h) fits inside another if both dimensions are strictly smaller. Sort by width ascending and, for equal widths, by height descending, then take the strict LIS of the heights. The descending tie-break stops two envelopes of equal width from chaining. For (5, 4), (6, 4), (6, 7), (2, 3) the answer is 3: (2, 3) inside (5, 4) inside (6, 7).

LCS of two permutations. If both sequences contain each value at most once, replace each element of the second by its position in the first; the LCS is then the LIS of that position list, in O(n log n) instead of the O(nm) table in the LCS article. Patience diff applies this to lines that appear exactly once in each file version, then recurses into the gaps, which is why it aligns moved functions more readably than a plain LCS diff.

Minimum deletions and covers. The fewest elements to remove to leave a sorted sequence is n - L. The minimum number of non-increasing subsequences needed to cover the sequence equals the strict LIS length (Mirsky's theorem, the dual of Dilworth's), which is why patience sorting uses exactly L piles.

How long is an LIS? Scaling measured

For a uniformly random permutation of n distinct values the expected LIS length approaches 2 sqrt(n) from below; the Baik-Deift-Johansson theorem gives the correction, about 2 sqrt(n) - 1.77 n^(1/6), with Tracy-Widom fluctuations. Measured with the function above on one random permutation per size:

At n = 1,000,000 the correction term predicts about 1,982, close to the measured 1,978. Two practical consequences follow. The tails array stays tiny on random-looking data (about 2,000 entries for a million elements), so the binary search is cheap and cache friendly. On nearly sorted data the opposite holds: L approaches n, so tails grows to O(n) entries. Separately, Erdos and Szekeres showed that any sequence of more than (r - 1)(s - 1) distinct numbers has an increasing subsequence of length r or a decreasing one of length s, so every long sequence hides a long monotone run.

Operational guidance

• Length only, streaming: the tails pass is online. You can maintain the LIS length of a stream in O(L) memory and O(log L) per element.
• Reconstruction: needs O(n) parent pointers. For very large inputs store them as a compact int32 array, or two-pass: compute the length first, then reconstruct only if needed.
• Records, not numbers: extract the key once into a list and run the method on keys, keeping indices back into the records. Define how ties in the key are handled before writing the comparator.
• Other languages: C++ has std::lower_bound and std::upper_bound for the two strictness modes; Java's Arrays.binarySearch returns an arbitrary match among equal keys, so write your own lower bound.

Failure modes

• Returning tails as the answer. Its length is right but its contents may not be a subsequence, as the worked example shows. Any code that returns tails will pass length-only tests and fail the first time a caller uses the elements.
• The wrong binary search. bisect_right where strictness was required lets equal values chain; bisect_left where non-decreasing was meant undercounts. Always include a test with repeated values.
• The wrong envelope tie-break. Sorting equal widths by ascending height lets (6, 4) chain into (6, 7) and overcounts.
• Quadratic code on large inputs. The O(n^2) version that passed review on 1,000 elements takes hours on a million. Put an input-size assertion or the fast method in the shared utility.
• Empty input. Both versions must return an empty list without indexing tail_idx[-1]; the code above guards it.

What to do next

1. Copy both functions and the random cross-check; add your own edge cases (empty, all equal, strictly decreasing, already sorted).
2. Trace the worked example by hand and confirm the final tails differ from the returned subsequence.
3. Solve the envelope problem, then break it by flipping the tie-break and confirm the test catches it.
4. Implement LCS of two permutations via LIS and compare its output and speed with the table method from the LCS article.
5. If you need counts, build the Fenwick version and test it against the O(n^2) count on small inputs.