The longest increasing subsequence, both ways

A single problem worth studying closely, because the two solutions demonstrate the two ways dynamic programming gets faster.

The quadratic version

def lis(nums):
    n = len(nums)
    length = [1] * n                    # every element alone is a chain of 1
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                length[i] = max(length[i], length[j] + 1)
    return max(length) if nums else 0

length[i] is the longest chain ending exactly at i. That pinning is what makes the recurrence possible, because the chain's last value is then known: it is nums[i].

The answer is max(length), not length[-1], because the best chain may end in the middle. Returning the last cell is a bug that passes on short inputs, where the best chain usually does end last.

The n log n version

from bisect import bisect_left

def lis_fast(nums):
    tails = []
    for n in nums:
        i = bisect_left(tails, n)
        if i == len(tails):
            tails.append(n)             # extends the longest chain
        else:
            tails[i] = n                # a better tail for that length
    return len(tails)

tails[k] is the smallest value that any chain of length k+1 can end on.

The insight: among chains of equal length, only the one with the smallest tail matters, because it can be extended by strictly more elements. Every other chain of that length is dominated and can be discarded.

tails is sorted by construction, so finding the position is a binary search.

Walking one through

nums = [10, 9, 2, 5, 3, 7, 101, 18]

10   tails = [10]
 9   tails = [9]              9 is a better tail than 10
 2   tails = [2]
 5   tails = [2, 5]
 3   tails = [2, 3]           3 is a better tail than 5
 7   tails = [2, 3, 7]
101  tails = [2, 3, 7, 101]
 18  tails = [2, 3, 7, 18]

answer 4

The warning

tails is not the answer. [2, 3, 7, 18] has the right length and is not necessarily a subsequence that exists in that order. Producing the actual sequence needs predecessor indices recorded as you go.

That is the same lesson as rolling a table: the compressed state carries the size, not the thing.

Variants that reuse it

Longest non decreasing uses bisect_right. Russian doll envelopes sorts by one dimension and runs this on the other. Minimum number of increasing subsequences to cover the array equals the length of the longest decreasing one.