Dynamic Programming for Longest Increasing Subsequence

Welcome back! In our previous lesson, we saw a clever trick in dynamic programming: reducing the Longest Palindromic Subsequence problem to the Longest Common Subsequence problem. This highlighted how recognizing underlying structures can simplify problem-solving.

Today, we shift our focus to another cornerstone of sequence DP: the Longest Increasing Subsequence (LIS) problem. Unlike our previous examples, LIS requires a unique DP state formulation. Mastering this pattern is crucial, as it appears in many variations. Our goal is to develop, understand, and implement an intuitive dynamic programming solution that runs in $O(N^2)$ time.

1. Defining the Longest Increasing Subsequence

First, let's establish our terms. A subsequence is created by deleting zero or more elements from an array while preserving the order of the remaining elements. An increasing subsequence is a subsequence where each element is strictly greater than the previous one. The Longest Increasing Subsequence is, therefore, the increasing subsequence with the maximum possible length.

For example, given the array A = [10, 22, 9, 33, 21, 50, 41, 60]:

• (10, 22, 21, 60) is a subsequence, but it's not increasing.
• (10, 22, 33) is an increasing subsequence of length 3.
• (10, 22, 33, 50, 60) is another increasing subsequence of length 5.
• The LIS is (10, 22, 33, 41, 60) or (10, 22, 33, 50, 60), both of which have a length of 6.

2. Formulating the DP State: A Common Pitfall

When first encountering a DP problem, our instinct might be to define the subproblem in the most obvious way. For LIS, we might try:

Let L(i) be the length of the LIS in the prefix A[0...i].

This seems logical, but it contains a hidden flaw. To see why, let's read a short section from a set of lecture notes from Dartmouth College that walks through a concrete example.

As the text explains, the problem is that L(i-1) (the length of the LIS in A[0...i-1]) doesn't tell us what number that subsequence ends with. Without that information, we don't know if we can legally append A[i] to it. For instance, in [20, 40, 10], the LIS is (20, 40). When we consider the next element, 30, we can't just append it to this LIS because 40 is not less than 30. The subproblem definition is missing crucial information.

3. The Correct DP State and Recurrence

To fix this, we need to redefine our subproblem to include the information we were missing. This leads to the canonical DP state for LIS:

Let dp[i] be the length of the Longest Increasing Subsequence that ends at index i.

This change is subtle but powerful. With this definition:

• The LIS ending at index i must include the element A[i].
• To find dp[i], we can look at all previous indices j < i. If A[j] < A[i], it means we can potentially extend an increasing subsequence that ended at j with the element A[i].
• We want to find the longest such previous subsequence to extend.

This gives us the following recurrence relation for dp[i]:

The + 1 accounts for the element A[i] itself. If no such j exists (i.e., A[i] is smaller than all previous elements), then dp[i] = 1, as A[i] forms an increasing subsequence of length 1 by itself.

Finally, since the LIS can end at any index, the overall answer is not dp[n-1], but rather the maximum value in the entire dp array. This is a common pitfall to watch out for.

The NeetCode video below provides an excellent walkthrough of this logic, deriving the $O(N^2)$ solution from scratch.

4. The $O(N^2)$ Implementation

The recurrence relation translates directly into a bottom-up algorithm. We'll create a dp array, initialize all its values to 1 (since every element is an LIS of at least length 1), and then iterate through the input array to fill it out.

Here is a typical Python implementation:

def length_of_lis(nums: list[int]) -> int:
    if not nums:
        return 0
    
    n = len(nums)



    # dp[i] will store the length of the LIS ending at index i
    dp = [1] * n
    



    # Iterate from the second element to the end
    for i in range(1, n):



        # Check all previous elements
        for j in range(i):



            # If we can extend the subsequence ending at j
            if nums[j] < nums[i]:



                # Update dp[i] if we found a longer path
                dp[i] = max(dp[i], 1 + dp[j])
    



    # The LIS can end at any index, so we need the max of the whole dp array
    return max(dp)




# Example from the problem description
nums1 = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"For {nums1}, LIS length is: {length_of_lis(nums1)}") # Expected: 4 -> (2, 3, 7, 101) or (2, 5, 7, 101) etc.




# Example from the image
nums2 = [1, 100, 6, 7, 9, 3, 4]
print(f"For {nums2}, LIS length is: {length_of_lis(nums2)}") # Expected: 4 -> (1, 6, 7, 9)

Let's trace nums = [1, 100, 6, 7, 9] to see how the dp array is filled.

• dp is initialized to [1, 1, 1, 1, 1].
• i = 0 (nums[0] = 1): dp[0] remains 1.
• i = 1 (nums[1] = 100):
  • j = 0: nums[0] < nums[1] (1 < 100). Update dp[1] = max(1, 1 + dp[0]) = 2.
  • dp is now [1, 2, 1, 1, 1].
• i = 2 (nums[2] = 6):
  • j = 0: nums[0] < nums[2] (1 < 6). Update dp[2] = max(1, 1 + dp[0]) = 2.
  • j = 1: nums[1] is not < nums[2]. No update.
  • dp is now [1, 2, 2, 1, 1].
• i = 3 (nums[3] = 7):
  • j = 0: nums[0] < nums[3] (1 < 7). Update dp[3] = max(1, 1 + dp[0]) = 2.
  • j = 1: nums[1] is not < nums[3]. No update.
  • j = 2: nums[2] < nums[3] (6 < 7). Update dp[3] = max(2, 1 + dp[2]) = 3.
  • dp is now [1, 2, 2, 3, 1].
• i = 4 (nums[4] = 9):
  • j = 0: nums[0] < nums[4]. dp[4] = max(1, 1 + dp[0]) = 2.
  • j = 1: not smaller.
  • j = 2: nums[2] < nums[4]. dp[4] = max(2, 1 + dp[2]) = 3.
  • j = 3: nums[3] < nums[4]. dp[4] = max(3, 1 + dp[3]) = 4.
  • dp is now [1, 2, 2, 3, 4].

The final dp array is [1, 2, 2, 3, 4]. The maximum value is 4, which is the correct length of the LIS.

Complexity Analysis

• Time Complexity: $O(N^2)$. The nested loops are the dominant factor. The outer loop runs $N$ times, and the inner loop runs up to $N$ times.
• Space Complexity: $O(N)$. We use an additional array dp of size $N$.

Conclusion

In this lesson, we dissected the Longest Increasing Subsequence problem and developed a robust $O(N^2)$ dynamic programming solution. We learned a valuable lesson in defining DP states: sometimes the most direct definition isn't the most useful, and we must refine the subproblem to carry the necessary information forward.

Key Takeaways:

• LIS Definition: A subsequence where each element is strictly greater than its predecessor.
• The Correct DP State: dp[i] is the length of the LIS ending at index i. This is the key insight.
• Recurrence Relation: dp[i] = 1 + max(dp[j]) for all j < i where A[j] < A[i].
• Final Answer: The solution is max(dp), not necessarily the last element of the DP array.
• Complexity: The straightforward implementation runs in $O(N^2)$ time and $O(N)$ space.

This $O(N^2)$ approach is a solid solution and a common interview expectation. However, the inner loop—which scans all previous dp values—is a performance bottleneck. In our next lesson, we will explore a more advanced technique using binary search to optimize this lookup, bringing the time complexity down to a remarkable $O(N\log N)$.