Longest Increasing Subsequence

Longest Increasing Subsequence is a classic dynamic-programming problem. It teaches the core DP move: define what one cell of a table means, then build the answer up from smaller subproblems you have already solved.

The slow way first

The brute-force idea: try every possible subsequence and keep the longest increasing one. There are 2^n subsequences, so checking them all is exponential — hopeless for anything but a tiny array.

The question to ask: what is a smaller piece of this problem I could solve and reuse? Instead of asking "what is the longest run overall," ask a narrower question for each position: "what is the longest increasing run that ends exactly here?" Those answers are easy to combine.

The idea

Let dp[i] be the length of the longest increasing subsequence that ends at index i. Every element on its own is a run of length 1, so dp starts as all 1s. To fill dp[i], look at every earlier index j < i: if nums[j] < nums[i], then the run ending at j can be extended by nums[i], giving a candidate length of dp[j] + 1. Take the best such candidate. The final answer is the largest value anywhere in dp.

The key insight: because we fill dp left to right, every dp[j] we read is already finished. We never recompute a subproblem — that is what turns the exponential search into a tidy nested loop.

Walk through it

Step through the animation. The top row is nums; the bottom row is dp, starting all 1s. Pointer i walks the input; for each i, pointer j scans the earlier elements.

At i = 3 (value 5), nums[2] = 2 is smaller, so dp[3] becomes dp[2] + 1 = 2. At i = 5 (value 7), the best smaller predecessor is 5 with dp[3] = 2, so dp[5] = 3 — the run 2, 5, 7. At i = 6 (value 101) it extends that to dp[6] = 4 — the run 2, 5, 7, 101. By the end dp = [1, 1, 1, 2, 2, 3, 4, 4], and the answer is max(dp) = 4.

Pseudocode

n = length of nums
dp = an array of n ones          # dp[i] = LIS ending at index i
for i from 1 to n - 1:
    for j from 0 to i - 1:
        if nums[j] < nums[i]:    # can we extend the run ending at j?
            dp[i] = max(dp[i], dp[j] + 1)
return the largest value in dp

The Python solution

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

• dp = [1] * n seeds every position with 1, since each element by itself is an increasing run of length 1.
• The outer loop fixes i, the element whose best run we are computing.
• The inner loop scans every earlier index j, looking for a smaller value we can build on.
• if nums[j] < nums[i] is the extendability check — the run ending at j can be followed by nums[i] only when nums[j] is strictly smaller.
• dp[i] = max(dp[i], dp[j] + 1) keeps the best run found so far for i.
• return max(dp) — the answer can end at any index, so we scan the whole table for the largest value.

Complexity

We trade O(n) extra space (the dp table) to collapse an exponential search into O(n²). A faster O(n log n) solution exists using binary search, but the O(n²) table is the version interviewers expect you to derive first.

When this pattern shows up

Practice