Maximum Subarray Sum: Dynamic Programming Techniques for Subarray Problems - LeetCode by Example

Problems covered in this article:

LeetCode 53. Maximum Subarray Sum (Easy)
LeetCode 718. Maximum Length of Repeated Subarray (Medium)

In previous articles, we covered the problem-solving steps and basic approaches for both one-dimensional and two-dimensional dynamic programming problems. However, mastering the basic steps alone is not enough. To become proficient at solving dynamic programming problems, you also need to acquire sufficient problem-solving techniques.

In the upcoming articles, I will explain specific tips for different types of dynamic programming problems. Today, we will focus on common techniques for problems involving subarrays.

Before diving into specific problems, let’s clarify the concepts of “subarray” and “subsequence”:

A subsequence can be non-contiguous. For example, “ACD” is a subsequence of “ABCDE”.
A subarray or substring must be contiguous. For example, “BCD” is a subarray/substring of “ABCDE”.

The Longest Common Subsequence problem we discussed in a previous example deals with “subsequences,” whereas in this article, we focus entirely on “subarrays” — keep this distinction in mind.

This article covers the following topics:

Dynamic programming techniques for subarray problems
Solution to the “Maximum Subarray Sum” problem
Solution to the “Longest Common Subarray” problem

Maximum Subarray Sum

LeetCode 53. Maximum Subarray Sum (Easy)

Given an integer array nums, find the contiguous subarray (containing at least one element) which has the largest sum and return its sum.

Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: The contiguous subarray [4,-1,2,1] has the largest sum = 6.

A Failed Attempt at Defining the Subproblem

When you first encounter this “Maximum Subarray Sum” problem, if you try to directly apply the four-step dynamic programming framework, you might initially think of defining the subproblem as follows:

Subproblem $f(k)$ represents “the maximum subarray sum in nums[0..k).”

Unfortunately, this subproblem definition does not work. The reason is that with this definition, we cannot derive a recurrence relation between subproblems!

Let’s look at a concrete example [-1, 2, 3, -2, 4, 1] and see the result for each subproblem:

$f(1)$ : the maximum sum subarray of [-1] is [-1], with sum -1;
$f(2)$ : the maximum sum subarray of [-1, 2] is [2], with sum 2;
$f(3)$ : the maximum sum subarray of [-1, 2, 3] is [2, 3], with sum 5;
$f(4)$ : the maximum sum subarray of [-1, 2, 3, -2] is [2, 3], with sum 5;
$f(5)$ : the maximum sum subarray of [-1, 2, 3, -2, 4] is [2, 3, -2, 4], with sum 7;
$f(6)$ : the maximum sum subarray of [-1, 2, 3, -2, 4, 1] is [2, 3, -2, 4, 1], with sum 8.

In the process of computing subproblems sequentially, there is a break in the recurrence from $f(4)$ to $f(5)$ :

$f(4)$ finds that the maximum sum subarray of [-1, 2, 3, -2] is [2, 3], which is located in the middle of the array.

When computing $f(5)$ , we add a new element 4. Naturally, we want to know if this new element can be combined with the optimal solution from $f(4)$ to produce the optimal solution for $f(5)$ . However, they cannot be combined!

The optimal solution of $f(4)$ , [2, 3], is not adjacent to the new element 4. They cannot be joined into a contiguous subarray!

Attempt to construct a recurrence relation for subproblems

As we can see, the problem lies in the “subarray” constraint. Subarrays require elements to be contiguous, so the optimal solution of a previous subproblem may not be usable in the next subproblem. The recurrence chain between subproblems breaks apart.

The Correct Subproblem Definition

So how do we solve this problem of subproblems that “cannot connect”? The answer is to modify the subproblem definition by adding a constraint:

Subproblem $f(k)$ represents “the maximum subarray sum in nums[0..k) that ends at the last element.”

Since subarrays cannot be spliced together, we restrict the subproblem’s subarray to the tail of the array. This way, the resulting maximum sum subarray can always be concatenated with the next element.

Let’s see how the subproblems are computed now:

$f(4)$ now finds the maximum subarray sum at the tail of [-1, 2, 3, -2], which is [2, 3, -2], with sum 3.
When computing $f(5)$ , we simply append the new element 4 to the previous optimal solution [2, 3, -2], yielding the maximum sum subarray [2, 3, -2, 4], with sum 7.

Recurrence Relation for Subproblems

With the correct subproblem definition, we can now write the recurrence relation. Using $n_i$ to denote the element nums[i], the recurrence formula is:

f(k) = \max \begin{cases} f(k-1) + n_{k-1} \\ n_{k-1} \end{cases}

The meaning of this recurrence is: when computing the maximum subarray sum of nums[0..k), we either append the new element nums[k-1] to the previous subproblem’s result (i.e., $f(k-1) + n_{k-1}$ ), or use only the element nums[k-1] alone, and we pick whichever option gives the larger result.

This recurrence can be further simplified to:

f(k) = \max \{ f(k-1), 0 \} + n_{k-1}

Now we can write the solution code:

public int maxSubArray(int[] nums) {
    // Subproblem:
    // f(k) = maximum subarray sum ending at nums[k-1] in nums[0..k)
	// Original problem = max{ f(k) }, 0 <= k <= N

    // f(0) = 0
    // f(k) = max{ f(k-1), 0 } + nums[k-1]

    int N = nums.length;
    int[] dp = new int[N+1];
    dp[0] = 0;

    int res = Integer.MIN_VALUE;
    for (int k = 1; k <= N; k++) {
        dp[k] = Math.max(dp[k-1], 0) + nums[k-1];
        res = Math.max(res, dp[k]);
    }
    return res;
}

Note that we cannot simply return the result of the last subproblem $f(n)$ . Because our subproblem definition has changed, $f(n)$ only computes the maximum subarray sum ending at the last element. We need to take the maximum over all subproblem results, i.e.,

\text{Final result} = \max_{0 \le k \le n} f(k)

Due to space constraints, we won’t discuss space optimization or alternative approaches for this problem here. A dedicated article covering different solutions to this problem will be written in the future.

Longest Common Subarray

Now that we understand the solution to the “Maximum Subarray Sum” problem, let’s look at a two-dimensional dynamic programming problem with a similar approach: the Longest Common Subarray.

LeetCode 718. Maximum Length of Repeated Subarray (Medium)

Given two integer arrays s and t, return the length of the longest common subarray. For example:
Input:
s: [1, 2, 3, 2, 1, 5]
t: [6, 3, 2, 1, 4, 7]
Output: 3
Explanation:
The longest common subarray is [3, 2, 1].

The “Longest Common Subarray” problem is actually similar to the “Longest Common Subsequence” problem, except that “subsequence” is replaced with “subarray.” If you are not very familiar with the “Longest Common Subsequence” problem, you can review the previous article:

LeetCode Problem Deep Dive | 15 Longest Common Subsequence: A Two-Dimensional Dynamic Programming Approach

In the “Longest Common Subsequence” problem, we defined the subproblem as:

Subproblem $f(i, j)$ represents “the longest common subsequence of s[0..i) and t[0..j).”

However, when the problem changes to “subarrays,” the properties of subarrays cause the original recurrence relation to break down, and we need to redefine the subproblem. Following the approach from the previous example, we add an at the tail of the array constraint to the subarray, defining the subproblem as:

Subproblem $f(i, j)$ represents “the longest common subarray of s[0..i) and t[0..j) that ends at the last element.”

Subproblem definition for the Longest Common Subarray problem

Note that ending at the last element here means the common subarray must include both the last element of s[0..i) and the last element of t[0..j).

In other words, we look backwards from the end of s[0..i) and t[0..j) to count how many consecutive elements are identical.

How do we define the recurrence relation for the subproblems? It’s straightforward — we just need to look at the last elements of s[0..i) and t[0..j): s[i-1] and t[j-1].

If s[i-1] == t[j-1], then there is already one matching element. Next, we continue looking backwards to count how many consecutive elements are identical in s[0..i-1) and t[0..j-1). That is, $f(i, j) = f(i-1, j-1) + 1$ .
If s[i-1] != t[j-1], then the last elements don’t match, so there’s no need to look further. That is, $f(i, j) = 0$ .

This gives us the recurrence formula:

f(i, j) = \begin{cases} f(i-1, j-1) + 1, & \text{if } s_{i-1} = t_{j-1} \\ 0, & \text{if } s_{i-1} \ne t_{j-1} \\ \end{cases}

How does the original problem relate to the subproblems? Like this:

\text{Final result} = \max_{0 \le i \le m, 0 \le j \le n} f(i, j)

Now we can write the solution code:

public int findLength(int[] s, int[] t) {
    // Subproblem:
    // f(i, j) = longest common subarray ending at s[i-1] and t[j-1] in s[0..i) and t[0..j)
    // Original problem = max{ f(i, j) }, 0 <= i <= m, 0 <= j <= n

    // f(0, *) = 0
    // f(*, 0) = 0
    // f(i, j) = max:
    //           f(i-1, j-1) + 1, if s[i-1] == t[j-1]
    //           0              , if s[i-1] != t[j-1]

    int m = s.length;
    int n = t.length;
    int[][] dp = new int[m+1][n+1];

    int res = 0;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else {
                if (s[i-1] == t[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = 0;
                }
            }
            res = Math.max(res, dp[i][j]);
        }
    }
    return res;
}

Summary

From the two examples above, we can see the common pattern for solving “subarray” problems. When defining subproblems, we add an at the tail of the array constraint. This is what makes it possible to properly derive the recurrence relation between subproblems.

The second example in this article, “Longest Common Subarray,” differs from “Longest Common Subsequence” by just one concept, yet the subproblem definitions and recurrence relations are quite different. I recommend working through both problems side by side — it will help you clearly appreciate the differences between “subarray” and “subsequence” problems. Here are the two problem links:

LeetCode 1143. Longest Common Subsequence (Medium)
LeetCode 718. Maximum Length of Repeated Subarray (Medium)

Beyond the examples in this article, there are several other “subarray” problems on LeetCode:

LeetCode 152. Maximum Subarray Product (Medium)
LeetCode 978. Longest Turbulent Subarray (Medium)

These are all classic subarray problems that are great for practice.