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*.