Longest increasing subsequence

Problem

A subsequence keeps the order of the original but may skip elements, unlike a substring. You want the longest one that is strictly increasing. Trying every subset is 2ⁿ. Two different tables avoid that: one indexed by where a subsequence ends, and one indexed by how long it is.

Intuition

Standing on a number, you ask: what is the longest increasing run that ends here? It is one more than the best run that ends on some earlier, smaller number, or just 1 if there is none. That is the whole quadratic idea.

For the faster version, flip the question. For each length k, what is the smallest number a run of length k can end on? A smaller ending is always at least as good for the future, since anything that can follow a large ending can also follow a small one. Keep these smallest endings in a list. They are always sorted, so a new number either goes after the end (the best run grows by one) or replaces the first ending that is not smaller than it (a run of that length now ends lower). Finding the spot is a binary search.

Bar height is the best run ending at that index. Blue bars lie on the run recovered by following parent links back from the best end. The diagram scrolls sideways on a narrow screen.

Mechanics

The O(n²) table

Let length[i] be the longest strictly increasing subsequence that ends exactly at index i. Then length[i] = 1 + max(length[j]) over all j < i with nums[j] < nums[i], or 1 if no such j exists. The answer is the largest entry, not the last one, because the best run need not end at the end. Store the j that gave the max in a parent array to recover an actual subsequence by walking back.

The tails list

Keep tails, where tails[k] is the smallest value that can end a strictly increasing subsequence of length k + 1. The invariant is that tails is strictly increasing. Proof sketch: if a subsequence of length k + 2 ends at v, dropping its last element gives one of length k + 1 ending at something less than v, so tails[k] < tails[k + 1].

Processing a value x: find the first index p where tails[p] >= x (a lower bound). If p is the end, append x; the longest run grew. Otherwise set tails[p] = x, since a run of length p + 1 can now end lower. The length of tails at the end is the answer. The contents of tails are not themselves a subsequence of the input, only a record of the best endings, which is the common mistake in reading it.

Each row is the tails list after reading the number on the left. The blue cell is the one that number wrote, either a new end or a replacement.

Invariant

After reading a prefix, tails[k] is the least possible last element over all strictly increasing subsequences of length k + 1 in that prefix. A new element x can extend the best run ending below x, and its length is the position found by the search, so it can only improve the entry at that position. Entries at other positions are unchanged, so the invariant is preserved.

Worked example

The sequence is 4, 10, 4, 3, 8, 9, 6, 11. The quadratic table of best run lengths ending at each index is 1, 2, 1, 1, 2, 3, 2, 4, so the answer is 4, for example 4, 8, 9, 11.

The tails version reads the numbers left to right. The final list is 3, 6, 9, 11, with length 4, the same answer. Look at the step for 6: it replaced 8 at slot 1, so the list now says a run of length 2 can end as low as 6. Yet the list 3, 6, 9, 11 is not a subsequence of the input, because 6 comes after 9 there. The length is right; the contents are only bookkeeping.

Counting: carrying a count next to each length shows that 3 different index choices give a longest run of 4.

Implementation

from bisect import bisect_left


def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)       # first slot not smaller than x
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)


def length_of_lis_quadratic(nums):
    if not nums:
        return 0
    length = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                length[i] = max(length[i], length[j] + 1)
    return max(length)

Variations and edge cases

from bisect import bisect_right


def non_decreasing_length(nums):
    tails = []
    for x in nums:
        i = bisect_right(tails, x)      # ties may extend, so go past equals
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)


def count_of_lis(nums):
    n = len(nums)
    length, count = [1] * n, [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                if length[j] + 1 > length[i]:
                    length[i], count[i] = length[j] + 1, count[j]
                elif length[j] + 1 == length[i]:
                    count[i] += count[j]
    best = max(length, default=0)
    return sum(c for l, c in zip(length, count) if l == best)


def russian_doll(envelopes):
    envelopes.sort(key=lambda e: (e[0], -e[1]))   # equal widths: taller first
    return length_of_lis([h for _, h in envelopes])

• Strict versus non-strict. Strict uses bisect_left and <; non-decreasing uses bisect_right and <=. Mixing them gives off-by-duplicates answers.
• Answer is the max, not the last entry of the quadratic table.
• Reading the tails list as the answer sequence. It is not one. To get a real sequence, record for each element the slot it landed in and its predecessor in slot - 1, then walk back.
• Equal widths in nesting problems. Sort the second key descending within equal first keys, so two with the same width can never both enter a chain.
• Empty input. Return 0; the quadratic code needs the guard before max.

Complexity and tradeoffs

• Time: O(n²) for the table, O(n log n) for the tails search.
• Space: O(n) in both (the tails list is at most n long).
• Baseline. Enumerating all subsequences is O(2ⁿ).
• Which to use. Start with the table when asked for the sequence itself, a count, or a variation with extra conditions; the table carries extra data easily. Use the tails list when n is large (about 10⁵) and only the length matters.
• When it fails. The tails trick relies on a total order, so it does not carry over directly to problems with extra constraints between chosen elements (such as a limit on the index gap), which usually need a segment tree or a monotonic deque over the table.

Problems

Longest Increasing Subsequence is the one list problem homed here. Its relatives, not on the lists, include counting the longest runs, nesting envelopes and removing the fewest elements to sort an array; the code above handles all of them with small changes.

Medium

• 300. Longest Increasing Subsequence Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Keep, for every length, the smallest tail value an increasing subsequence of that length can end with, and binary-search each new value into place.

Connections

The tails search is a binary search on a sorted structure that you maintain yourself, and it is also the first step of patience sorting. The quadratic table is linear DP with a "look back at every smaller value" transition. Longest Increasing Path in a Matrix carries the same idea to a graph, where memoized DFS replaces the loop over earlier positions.

Check yourself

References

• Schensted, C., "Longest increasing and decreasing subsequences", Canadian Journal of Mathematics 13, 1961.
• Fredman, M. L., "On computing the length of longest increasing subsequences", Discrete Mathematics 11(1), 1975.
• Aldous and Diaconis, "Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem", Bulletin of the AMS 36, 1999.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 14, the longest increasing subsequence exercise.
• Sedgewick and Wayne, Algorithms, section 1.1: the binary search the patience-sorting version runs over the pile tops.
• Skiena, The Algorithm Design Manual: the dynamic programming chapter, which works the longest increasing subsequence as an example.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.