Longest increasing subsequence

The longest increasing subsequence is a classic DP with two solutions: a simple table that takes O(n²) time (time that grows with n multiplied by n), and a cleverer one with binary search that takes O(n log n). The second shows how a DP can keep a different kind of state to go faster.

The problem

A subsequence of a list keeps some of its values in their original order and skips the others. It differs from a stretch (DVCQ-1), whose values must be side by side. In [5, 2, 8, 6, 3, 6, 9, 7], both [2, 3, 6, 9] and [5, 6, 9] are subsequences. A subsequence is increasing (here: strictly rising) if each value is larger than the one before it. Find the length of the longest one.

A list of n values has 2ⁿ subsequences (each value is kept or skipped, so n twos multiplied together), so trying them all is hopeless beyond about 25 values.

The O(n²) table

The best subsequence can end anywhere, so fix where it ends (lesson 4). Let len[i] be the length of the longest increasing subsequence that ends with the value at position i. The value before a[i] in such a subsequence is some a[j] with j < i and a[j] < a[i], and the part up to it must be as long as possible. So len[i] is 1 plus the largest len[j] over those j, or just 1 if there are none. The answer is the largest len[i].

def lis_length(a):
    length = [1] * len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i] and length[j] + 1 > length[i]:
                length[i] = length[j] + 1
    return max(length, default=0)

Every pair j < i is checked once: about n²/2 comparisons, half of n multiplied by n. For 10,000 values that is 50 million, a few seconds in Python; for 100,000 values it is far too slow.

Tails and binary search

The second version of the figure keeps a different list. tails[k] is the smallest value that ends an increasing subsequence of length k + 1 among the values seen so far. A small last value is better than a large one, because more later values can follow it. For each new value x, find the first tail that is not smaller than x. If there is none, x extends the longest subsequence; otherwise x replaces that tail.

from bisect import bisect_left

def lis_length(a):
    tails = []
    for x in a:
        k = bisect_left(tails, x)   # first tail >= x
        if k == len(tails):
            tails.append(x)          # a longer subsequence
        else:
            tails[k] = x             # a smaller end for length k + 1
    return len(tails)

tails always rises (proved below), so bisect_left can search it (BSRC). Each value costs one binary search: O(n log n) in all, about 1.7 million comparisons for 100,000 values instead of 5 billion.

Why the tails method is right

Two facts, each kept true after every value.

1. tails rises strictly. Take a subsequence of length k + 2 that ends with tails[k + 1]. Its value before the last is smaller than tails[k + 1], and it ends a subsequence of length k + 1. So the smallest such end, tails[k], is smaller than tails[k + 1] too.
2. Each update is right. A new value x can extend a subsequence of length m exactly when some subsequence of length m ends with a value smaller than x, that is, when tails[m − 1] < x. Since tails rises, these are the first k positions, where k = bisect_left(tails, x). So x ends a subsequence of length k + 1 and no longer. If tails[k] exists, it is at least x, so x is the new smallest end for that length. Other entries do not change: x cannot end a longer subsequence, and for shorter lengths the old ends are already smaller than x.

After the last value, the longest length with an entry in tails is the answer. Note that tails is a list of ends of different subsequences: it is often not a subsequence of the input at all. Lesson 9 shows how to rebuild a real one.

Variants

• Never falling (equal values allowed): use bisect_right, so an equal value extends instead of replacing.
• Longest decreasing: run the same code on the negated values, [-x for x in a].
• Two sizes at once, such as boxes that must be smaller in width and height: sort by one size, then find an increasing subsequence of the other. Equal first sizes need care: DYNP-P6.
• The fewest falling subsequences that together use every value equals the length of the longest increasing subsequence. The card game patience shows why: deal the values one by one onto piles, each onto the first pile whose top is at least as large, or onto a new pile. Each pile is a falling subsequence, the number of piles is the answer, and the tops of the piles are exactly tails.

Now try DYNP-P6, Nesting boxes.