230. Longest Increasing Subsequence

Why this mechanism works

For each endpoint i, consider every earlier smaller value j and extend the best subsequence ending there. This yields a direct, inspectable recurrence. The optimized view groups subsequences by length instead: retain the smallest possible ending value for each length, because a smaller tail is at least as easy to extend later.

State and boundaries

dp[i] is the LIS length ending exactly at i. In the optimized version, tails[length-1] is the smallest achievable tail for that subsequence length among processed positions.

Protocol

1. Initialize each ending-at-index length to one.
2. Extend from every earlier strictly smaller value.
3. Take the maximum for the reference DP.
4. For optimized search, find the first tail >=current.
5. Replace it, or append when no such tail exists.

Visualization

nums [3,1,2,2,4]
tails [3] -> [1] -> [1,2] -> [1,2] -> [1,2,4]
the repeated 2 replaces; it does not extend

From the recurrence to the optimized solution

Start with the state you can prove: dp[i] answers a question about one fixed endpoint. For [3,1,2,2,4], the table becomes [1,1,2,2,3]. The final answer is max(dp), because the optimum may end anywhere.

Now ask which information an unseen future value needs. For subsequences of equal length, only their smallest ending value matters for future extension. A length-two subsequence ending at 2 is at least as useful as one ending at 8. This is a dominance argument: discard the worse tail, not a potentially larger length.

The tails array is strictly increasing. A length-(k+1) subsequence contains a length-k prefix with a smaller endpoint, so the minimum tail for length k is smaller than the minimum tail for length k+1. Binary search is therefore valid. The first tail >=x is the length whose ending value x can improve; every earlier tail is strictly smaller than x and can be extended by it. Equality replaces instead of appending.

Remember the boundary with the earlier binary-search chapter: bisect_left finds the first index where tail>=x. It is the same false-then-true predicate, expressed through a standard-library function. If every tail is smaller, the returned index is len(tails), the valid insertion boundary for a new longest length.

Do not infer that the current tails entries belong to the same historical route. They summarize separate best endpoints. To recover a route, preserve predecessor indices when each input value changes a tail.

Python implementation

from bisect import bisect_left

def lis_quadratic(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

def lis_length(nums):
    tails = []
    for value in nums:
        i = bisect_left(tails, value)
        if i == len(tails):
            tails.append(value)
        else:
            tails[i] = value
    return len(tails)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 lis_quadratic: dp = [1] * len(nums)
nums=[10, 9, 2, 5, 3, 7, 101, 18]; dp=[1, 1, 1, 1, 1, 1, 1, 1]

L5 lis_quadratic: for i in range(len(nums)):
nums=[10, 9, 2, 5, 3, 7, 101, 18]; dp=[1, 1, 1, 1, 1, 1, 1, 1]; i=0

L5 lis_quadratic: for i in range(len(nums)):
nums=[10, 9, 2, 5, 3, 7, 101, 18]; dp=[1, 1, 1, 1, 1, 1, 1, 1]; i=1

L6 lis_quadratic: for j in range(i):
nums=[10, 9, 2, 5, 3, 7, 101, 18]; dp=[1, 1, 1, 1, 1, 1, 1, 1]; i=1; j=0

L5 lis_quadratic: for i in range(len(nums)):
nums=[10, 9, 2, 5, 3, 7, 101, 18]; dp=[1, 1, 1, 1, 1, 1, 1, 1]; i=2; j=0

L6 lis_quadratic: for j in range(i):
nums=[10, 9, 2, 5, 3, 7, 101, 18]; dp=[1, 1, 1, 1, 1, 1, 1, 1]; i=2; j=1

L5 lis_quadratic: for i in range(len(nums)):
nums=[10, 9, 2, 5, 3, 7, 101, 18]; dp=[1, 1, 1, 1, 1, 1, 1, 1]; i=3; j=1

L6 lis_quadratic: for j in range(i):
nums=[10, 9, 2, 5, 3, 7, 101, 18]; dp=[1, 1, 1, 1, 1, 1, 1, 1]; i=3; j=0

... 34 intermediate state changes omitted ...

L6 lis_quadratic: for j in range(i):
nums=[10, 9, 2, 5, 3, 7, 101, 18]; dp=[1, 1, 1, 2, 2, 3, 4, 3]; i=7; j=4

L6 lis_quadratic: for j in range(i):
nums=[10, 9, 2, 5, 3, 7, 101, 18]; dp=[1, 1, 1, 2, 2, 3, 4, 3]; i=7; j=5

L8 lis_quadratic: dp[i] = max(dp[i], dp[j] + 1)
nums=[10, 9, 2, 5, 3, 7, 101, 18]; dp=[1, 1, 1, 2, 2, 3, 4, 4]; i=7; j=5

L6 lis_quadratic: for j in range(i):
nums=[10, 9, 2, 5, 3, 7, 101, 18]; dp=[1, 1, 1, 2, 2, 3, 4, 4]; i=7; j=6

L12 lis_length: tails = []
nums=[3, 1, 2, 2, 4]; tails=[]

L13 lis_length: for value in nums:
nums=[3, 1, 2, 2, 4]; tails=[]; value=3

L14 lis_length: i = bisect_left(tails, value)
nums=[3, 1, 2, 2, 4]; tails=[]; value=3; i=0

L16 lis_length: tails.append(value)
nums=[3, 1, 2, 2, 4]; tails=[3]; value=3; i=0

L13 lis_length: for value in nums:
nums=[3, 1, 2, 2, 4]; tails=[3]; value=1; i=0

L18 lis_length: tails[i] = value
nums=[3, 1, 2, 2, 4]; tails=[1]; value=1; i=0

L13 lis_length: for value in nums:
nums=[3, 1, 2, 2, 4]; tails=[1]; value=2; i=0

L14 lis_length: i = bisect_left(tails, value)
nums=[3, 1, 2, 2, 4]; tails=[1]; value=2; i=1

L16 lis_length: tails.append(value)
nums=[3, 1, 2, 2, 4]; tails=[1, 2]; value=2; i=1

L13 lis_length: for value in nums:
nums=[3, 1, 2, 2, 4]; tails=[1, 2]; value=4; i=1

L14 lis_length: i = bisect_left(tails, value)
nums=[3, 1, 2, 2, 4]; tails=[1, 2]; value=4; i=2

L16 lis_length: tails.append(value)
nums=[3, 1, 2, 2, 4]; tails=[1, 2, 4]; value=4; i=2

Why the solution is correct

The endpoint recurrence considers every possible penultimate index, so it gives exact ending lengths. For tails, replacing the first value >=current preserves feasible lengths while improving their extension opportunities; appending means current extends the longest known length. The tails length therefore equals the optimum, although its entries need not form one actual subsequence.

Time and space

Reference: O(n^2) time and O(n) space. Optimized: O(n log(n+1)) time and O(n) space. Both leave input unchanged.

Common mistakes

Using upper_bound instead of lower_bound changes strict increasing to nondecreasing. Returning tails as the actual subsequence is not justified by its invariant.

Reasoning card

Transfer exercise

Reconstruct an actual LIS using predecessor indices and the input index associated with each current tail.