Chapter 8: Sequences and Subsequences - Longest Increasing Subsequence

We now transition to another major category of dynamic programming problems: those involving sequences or strings. Instead of moving on a grid or making change, we will be analyzing an array to find a subsequence with specific properties.

The "Longest Increasing Subsequence" (LIS) problem, LeetCode #300, is a classic that every programmer should know. It introduces a common DP pattern where the state dp[i] represents the solution for a subproblem that must end at index i.

The Problem:

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of [0,3,1,6,2,2,7].

For example:

• nums = [10,9,2,5,3,7,101,18] -> The answer is 4. The longest increasing subsequence is [2,3,7,101].

• nums = [0,1,0,3,2,3] -> The answer is 4.

• nums = [7,7,7,7,7,7,7] -> The answer is 1.

Approach 1: The Recursive Solution (Brute-Force)

Let's define a recursive function lis_ending_at(i) that computes the length of the longest increasing subsequence ending at index i.

To find this, we need to look at all previous elements j (where j < i). If nums[i] is greater than nums[j], it means we can potentially extend the increasing subsequence that ends at j. We find the maximum length among all such valid previous subsequences and add 1 (for nums[i] itself).

The base case is a subsequence of one element, which always has a length of 1.

The final answer will be the maximum value of lis_ending_at(i) for all i in the array.

from typing import List

def lengthOfLIS_recursive(nums: List[int]) -> int:

    memo = {}
    def lis_ending_at(i):
        if i in memo:
            return memo[i]

        # Base case: a single element is an increasing subsequence of length 1.
        max_len = 1

        # Look at all previous elements.
        for j in range(i):
            if nums[i] > nums[j]:
                # If we can extend the subsequence ending at j...
                max_len = max(max_len, 1 + lis_ending_at(j))

        memo[i] = max_len
        return max_len

    # The result is the maximum LIS length ending at any index.
    return max(lis_ending_at(i) for i in range(len(nums))) if nums else 0

# Trying it out
# print(lengthOfLIS_recursive([10,9,2,5,3,7,101,18])) # Output: 4
# This version is actually memoized, a pure recursion would be even slower.
# A pure recursive version would be O(2^n).

Even with the explicit dictionary memo, this top-down approach shows the core logic. A pure brute-force without memoization would be extremely slow as it would recompute the LIS for the same indices repeatedly.

Approach 2: Memoization with a Decorator (Top-Down DP)

The solution above is already memoized, but we can make it cleaner with our familiar decorator. This formalizes the caching process and keeps the core logic separate.

import functools
from typing import List

class Solution:
    def lengthOfLIS_memoized(self, nums: List[int]) -> int:

        @functools.lru_cache(maxsize=None)
        def lis_ending_at(i):
            max_len = 1
            for j in range(i):
                if nums[i] > nums[j]:
                    max_len = max(max_len, 1 + lis_ending_at(j))
            return max_len

        if not nums:
            return 0

        return max(lis_ending_at(i) for i in range(len(nums)))

# Trying it out
# solver = Solution()
# print(solver.lengthOfLIS_memoized([10,9,2,5,3,7,101,18])) # 4

This top-down DP solution has a time complexity of O(n^2) because for each index i, we might look at all i-1 previous indices. Since each state lis_ending_at(i) is computed only once, it's efficient enough for moderate constraints.

Approach 3: Iteration (Bottom-Up DP)

For the bottom-up approach, we'll create a dp array where dp[i] stores the length of the LIS ending at index i.

1. Create a dp array of the same size as nums, and initialize all its values to 1 (since every element is an LIS of length 1 by itself).

2. Iterate with i from 1 to n-1 (the element we are trying to calculate the LIS for).

3. For each i, have an inner loop with j from 0 to i-1 (the previous elements).

4. If nums[i] > nums[j], it means we can extend the LIS that ends at j. We update dp[i] with the maximum of its current value and 1 + dp[j].

5. After the loops, the answer is not necessarily dp[n-1], but the maximum value in the entire dp array, because the LIS could end at any index.

def lengthOfLIS_iterative(nums: List[int]) -> int:
    if not nums:
        return 0

    n = len(nums)
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], 1 + dp[j])

    return max(dp)

# Trying it out
# print(lengthOfLIS_iterative([10,9,2,5,3,7,101,18])) # 4

This bottom-up solution is also O(n^2) and is often the most common and intuitive DP solution for this problem.

(Note: There is a more advanced solution using binary search that achieves O(n log n) time complexity, but the O(n^2) approach is the canonical dynamic programming solution and a crucial pattern to master first.)

Conclusion

This chapter introduced a new perspective on the DP state. By defining dp[i] as the solution for a subproblem that ends at i, we were able to build a solution by looking backward at previous optimal solutions. This pattern is fundamental for many sequence-based problems, where the solution at a given point depends on the properties of the elements that came before it.