LIS Family

The Longest Increasing Subsequence (LIS) asks for the longest chain of elements that keeps the original order and strictly increases. The same shape covers chains of pairs, nested envelopes and counting how many longest chains exist. You'll learn two ways to solve it: a simple $O(n^2)$ DP, and a faster $O(n \log n)$ version with binary search for when n gets large.

The idea#

Let length[i] be the length of the longest increasing subsequence that ends at i. Any such chain is some chain ending at an earlier j with nums[j] < nums[i], plus nums[i]:

length[i] = 1 + max(length[j] for j < i if nums[j] < nums[i]), or 1 if there's no such j.

The answer is max(length), not length[-1], because the best chain can end anywhere.

That gives you the $O(n^2)$ DP. To get to $O(n \log n)$, you need a different state: keep tails[k] = the smallest possible last value of an increasing subsequence of length k + 1. Why does this work? A smaller tail is always at least as good, because it leaves more room for future elements. Each new number either extends the longest chain or replaces the first tail that is >= it.

How to spot it#

The word "subsequence" is the strongest clue, but the chain is often hidden in pairs or boxes. Look for these signals in the question.

• "Subsequence" (order kept, gaps allowed) plus "increasing", "chain", "nested", "each must be bigger than the last".
• Pairs or boxes that must fit inside each other after sorting.
• n up to about 2500 for $O(n^2)$; larger needs the bisect version.

Template#

Start with the $O(n^2)$ shape, which is the recurrence from above as two loops. Each position looks back at every earlier one.

length = [1] * n                  # longest chain ending at i
for i from 0 to n - 1:
    for j from 0 to i - 1:
        if nums[j] < nums[i]:     # i can extend the chain ending at j
            length[i] = max(length[i], length[j] + 1)
return max of length (0 if empty)

The fast version: tails and binary search#

When n is too large for the double loop, switch to the tails list from the idea section. It stays sorted, so for each number you can binary search for the first tail that is >= it.

tails = empty list                # tails[k]: smallest end of a k+1 chain
for each x in nums:
    k = first index with tails[k] >= x     # bisect_left
    if k == length of tails:
        append x                  # x extends the longest chain
    else:
        tails[k] = x              # x is a better (smaller) tail
return length of tails

The replace step is the part that feels odd at first, so it helps to watch it run. Here is the trace for [10, 9, 2, 5, 3, 7, 101, 18]:

tails isn't itself an increasing subsequence of the input. Only its length is the answer.

Pitfalls#

The first two are easy to slip into on the basic problem. The rest show up in the variations below.

• Returning length[-1] instead of max(length).
• Using bisect_right for a strictly increasing LIS. It allows equal values; bisect_left doesn't.
• When counting chains, adding to the count when a longer chain appears instead of resetting it.
• Sorting 2-D items for nesting without thinking about ties. The tie-break decides whether equal sizes can nest.
• Writing "try every unused item" with a shared used[] list and @cache. The cache ignores used; a sort plus LIS needs no such list.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below.

• 674. Longest Continuous Increasing Subsequence
• 300. Longest Increasing Subsequence
• 673. Number of Longest Increasing Subsequence
• 646. Maximum Length of Pair Chain
• 354. Russian Doll Envelopes

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• length[i] is the best chain ending at i; the answer is the max over all i.
• tails with bisect_left gives $O(n \log n)$ and only its length is meaningful.
• To count chains, reset the count on a longer length and add on an equal one.
• Turn 2-D nesting into 1-D LIS with a careful sort and tie-break.