Longest Increasing Subsequence

Longest Increasing Subsequence is the clearest lesson in choosing the state. The obvious state does not work, the right one is "ending at i", and after that the table is short. Then there is a twist: a faster answer that leaves DP behind and uses binary search.

Interviewers ask for the O(n²) version first and then ask "can you do better?" — so know both.

The problem

Given a list of integers, return the length of the longest strictly increasing subsequence — numbers taken in their original order, not necessarily next to each other, each bigger than the one before.

• [3, 1, 8, 2, 5, 9, 4, 6] → 4. For example 1, 2, 5, 9 or 1, 2, 4, 6.
• [7, 7, 7] → 1. Equal numbers are not increasing.

Constraints: 1 ≤ n ≤ 2,500, values between −10⁴ and 10⁴. (The follow-up raises n to 10⁵.)

Clarifying questions

• Strictly increasing, or non-decreasing? Strictly. Non-decreasing is a one-word change at the end.
• Length, or the subsequence? Length.
• Contiguous? No — that would be a much easier sliding scan.

Approach 1: the simple way — take or skip, remembering the last value

Walk the list; for each number, skip it or take it — but you may only take it if it is bigger than the last number taken. So the recursion needs two things: where you are, and the last index taken.

1def lis_rec(nums: list[int]) -> int:2    """longest(i, prev): best from nums[i:], all bigger than nums[prev]."""3    def longest(i: int, prev: int) -> int:4        if i == len(nums):5            return 06        best = longest(i + 1, prev)                      # skip nums[i]7        if prev == -1 or nums[i] > nums[prev]:8            best = max(best, 1 + longest(i + 1, i))      # take nums[i]9        return best10    return longest(0, -1)                                # -1: nothing taken yet

Why it is too slow. On a list that is already increasing, every number can be taken or skipped, so the calls double at each step: 2,047 for n = 10, 2,097,151 for n = 20. At n = 2,500 it never ends. But the pairs (i, prev) number only about n², so a cache fixes it — and the fact that the recursion needs prev at all is the hint for the real state.

The key insight

Try the obvious state first: "dp[i] = the longest increasing subsequence within the first i numbers". It cannot be extended. To know whether nums[i] can go on the end, you need to know what the best subsequence ends with, and this state does not say.

So put the ending into the state: dp[i] = the length of the longest increasing subsequence that ends exactly at index i. Now extending is easy. Any earlier j with nums[j] < nums[i] has a subsequence that nums[i] can finish:

dp[i] = 1 + max(dp[j] for j < i with nums[j] < nums[i]),   or 1 if there is no such janswer = max(dp)        — the best subsequence can end anywhere

Approach 2: memoisation

1from functools import cache23def lis_memo(nums: list[int]) -> int:4    @cache5    def longest(i: int, prev: int) -> int:6        if i == len(nums):7            return 08        best = longest(i + 1, prev)9        if prev == -1 or nums[i] > nums[prev]:10            best = max(best, 1 + longest(i + 1, i))11        return best12    return longest(0, -1)

About n² states of O(1) work: O(n²) time and space, and the stack is n deep. It works, but the table below uses only O(n) space.

Approach 3: the O(n²) table

1def lis_table(nums: list[int]) -> int:2    """dp[i] = length of the longest increasing subsequence ending at i."""3    dp = [1] * len(nums)                 # nums[i] alone4    for i in range(len(nums)):5        for j in range(i):6            if nums[j] < nums[i]:7                dp[i] = max(dp[i], dp[j] + 1)   # extend the run ending at j8    return max(dp)

Dry run on [3, 1, 8, 2, 5, 9, 4, 6]:

max(dp) = 4. Note the answer is not dp[-1] in general — here it happens to be 4 at both i = 5 and i = 7.

Complexity: O(n²) time, O(n) space. For n = 2,500 that is about 3 million comparisons — fine. For n = 10⁵ it is 5 × 10⁹ — far too slow.

Approach 4: O(n log n) with a list of tails

Keep a list tails where tails[k] is the smallest possible last value of an increasing subsequence of length k + 1 seen so far. Two facts make it work:

1. tails is always sorted. A length-3 subsequence ends higher than the best length-2 one inside it, so longer lengths have bigger tails.
2. A smaller tail is always better. A subsequence ending in 4 accepts every number that one ending in 5 accepts, and also 5 itself.

So for each number x: find the first tail that is ≥ x with binary search. If there is none, x extends the longest subsequence — append it. Otherwise replace that tail with x: you now have a subsequence of that length ending lower.

1import bisect23def length_of_lis(nums: list[int]) -> int:4    """O(n log n): tails[k] = smallest last value of an increasing run of length k+1."""5    tails: list[int] = []6    for x in nums:7        k = bisect.bisect_left(tails, x)     # first tail >= x8        if k == len(tails):9            tails.append(x)                  # x extends the longest run10        else:11            tails[k] = x                     # a lower ending for length k+112    return len(tails)

Dry run on the same list:

Length 4, the same as the table. Complexity: one binary search per number, O(n log n) time; O(n) space. For n = 10⁵ that is about 1.7 million steps instead of 5 billion.

This is no longer really DP — there is no table of answers per state — but it grows out of the DP view: "for each length, what is the best ending?".

Edge cases

• One number — the answer is 1.
• All equal — [7, 7, 7]: bisect_left finds the existing 7 each time and replaces it, so the answer stays 1. That is what "strictly" needs.
• Strictly decreasing — every number replaces tails[0]; the answer is 1.
• Already increasing — every number is appended; the answer is n.

Follow-ups

• Non-decreasing instead of strictly increasing — use bisect_right, so an equal number extends instead of replacing.
• Return the subsequence itself — with the O(n²) table, keep a parent[i] = the j that gave dp[i], and walk back from the best i. The tails list alone is not enough (see the warning).
• Nested envelopes (Russian doll) — sort by width ascending and, for equal widths, height descending; then the answer is the LIS of the heights.
• Number of longest subsequences — keep a count next to each dp[i] and add counts when a dp[j] + 1 ties the best.