LeetCode 53: Maximum Subarray

The maximum subarray problem is famous enough to have its own Wikipedia page, and a named algorithm you can use to solve it (Kadane’s Algorithm). But rather than looking up the algorithm, we’ll derive the solution to LeetCode 53: Maximum Subarray using principles of dynamic programming.

The problem statement is simple. Here’s the LeetCode version:

Given an integer array nums, find the subarray with the largest sum, and return its sum.

A subarray is a contiguous and non-empty sequence of elements from the input array. So we’re looking for the largest sum of all values from nums[i] to nums[j] (inclusive), where i <= j.

Maximum Subarray

Here’s a heuristic that often works to solve simpler dynamic programming problems: Consider an array of the same size as the input array and look for a way to calculate the optimal solution at each position. For this problem, our array would record the largest sum for all subarrays ending at position i.

Let’s call our array dp. Then dp[0] is just nums[0], since at position 0, we only have one element to consider, so it must be the largest (since the empty sequence isn’t allowed). For dp[1], the optimal value is either dp[0] + nums[1] or just nums[1]. For example, if nums is [-1, 1] then we don’t want to include nums[0] in the subarray, since it will decrease the sum.

What about dp[2]? We could add nums[2] to dp[1] and see if it makes a larger value than nums[2] alone. This is the same process we used for dp[1]. So we have the dynamic programming elements we need to implement a solution:

• Subproblems: dp[i] is the largest sum for elements through position i. If nums has n elements, then the overall solution will end up in dp[n-1].

• Base case: We saw that dp[0] == nums[0], so we can use i == 0 as the base case.

• Approach: Since we’re filling dp in order, starting with the base case, our solution will be a bottom-up approach.

• State: To identify a state, we just need one variable i, which tells us the ending position in nums for the current subproblem.

• State transition: Using the process explained above, our state transition equation is dp[i] = max(dp[i-1] + nums[i], nums[i]).

Putting this all together gives us this pseudocode:

dp[0] = nums[0]
maxSum = nums[0]

for i from 1 to nums.Length-1
    dp[i] = max(dp[i-1] + nums[i], nums[i])
    maxSum = max(maxSum, dp[i])

return maxSum

But this solution doesn’t use every element of dp. In fact, it only uses two elements: the current one, dp[i], and the previous one, dp[i-1]. So we can turn this into an $O(1)$ space solution by replacing the full dp array with one variable, prev.

prev = nums[0]
maxSum = nums[0]

for i from 1 to nums.Length-1
    prev = max(prev + nums[i], nums[i])
    maxSum = max(maxSum, prev)

return maxSum

When you’re solving a dynamic programming problem, it’s useful to start by assuming you have an array to store solutions to every subproblem. But for simpler problems, you may find that you don’t need the entire array.

(Image credit: DALL·E 3)

For an introduction to this year’s project, see A Project for 2024.