Lesson 50 — DP IV: longest increasing subsequence

Day 64 · ~25 minutes · DP ending-at-i state · Python

Tonight's problem is Longest Increasing Subsequence. Interviewers like it because it punishes fuzzy DP: the answer is not just “use an array.” You must say exactly what each cell means. A subsequence keeps order but may skip items (subsequence definition), so the key move is to ask which earlier endings can legally attach to the current number.

The invariant

Memorize this
Define dp[i] as the best subsequence ending exactly at i: one more than the best dp[j] over all j < i with nums[j] < nums[i].

The slow way first

The brute force idea is to try every subsequence: for each number, choose it or skip it, then keep only the increasing ones. That is O(2ⁿ) time, because the number of choose/skip combinations doubles with each new element. Dynamic programming is the escape hatch: store answers to smaller overlapping subproblems instead of rebuilding them (dynamic programming).

The DP state

Make dp[i] mean one narrow thing: the best increasing subsequence that must end at index i. If nums[j] < nums[i], any subsequence ending at j can extend into i. If not, that previous state cannot attach.

Code it straight from the invariant. Every cell starts at 1, because a single number is an increasing subsequence by itself.

def lengthOfLIS(nums):
    dp = [1] * len(nums)              # each item alone has length 1
    for i in range(len(nums)):
        for j in range(i):            # only earlier endings can attach
            if nums[j] < nums[i]:     # increasing rule
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)                    # best ending can be anywhere

The return line matters. dp[-1] only means “best subsequence ending at the final index.” The real answer is the best ending across all indices, so use max(dp). Python's range and max are built-ins you will use constantly in loops like this (range docs, max docs).

Transfer: same state, tiny twist

Mini problem: find the longest non-decreasing subsequence, where equal neighbors are allowed. Before opening the reveal, predict the one line that changes.

Your prediction first — then reveal.

The state stays identical: dp[i] is still the best subsequence ending exactly at i. Only the attach rule changes from nums[j] < nums[i] to nums[j] <= nums[i].

if nums[j] <= nums[i]:
    dp[i] = max(dp[i], dp[j] + 1)

What the trade buys you

Approach	Time	Space
Brute force (try every subsequence)	O(2ⁿ)	O(n)
DP ending-at-i state	O(n²)	O(n)

Practice — answer before you scroll past

1. What does dp[i] mean in this lesson?

The word “ending” is the whole state. Once the subsequence must end at i, every valid previous ending j becomes a candidate parent.

2. For nums = [2, 5, 3, 7], which previous indices can extend into value 7?

All earlier values are smaller than 7, so all three earlier endings are legal parents. The transition chooses the parent with the largest dp[j].

3. Spot the bug in this transition:

if nums[j] < nums[i]:
    dp[i] = max(dp[i], dp[j])

Extending a subsequence ending at j means adding nums[i] as one more item, so the candidate length is dp[j] + 1.

4. Where is the final LIS length after filling dp?

The best subsequence may end before the final index. dp[i] is local to one ending position; max(dp) collects the global best.

Your move (tonight)

Solve Longest Increasing Subsequence in your Notion tracker using the cycle — predict → attempt → compare → encode. In the predict step, say the brute force and the invariant out loud. In the encode step, write the state, transition, base case, and answer location in four short sentences.

One primary source

Watch NeetCode — Longest Increasing Subsequence after your attempt, as the compare step. Listen for how he chooses what dp[i] means before writing the loops.