The Maximum Subarray Problem

The Problem

Given an array of numbers AA of size nn, find a contiguous non-empty subarray with the largest sum. That is, find

max0ij<nk=ijA[k].\max_{0 \le i \le j < n} \sum_{k=i}^j A[k].

Examples

The Pathological Example

For A=[]A = [ ] assume the solution is -\infty. Or 00. Or whatever you prefer.

The Simplest Example

For A=[1]A = [1] the solution is 11. The subarray is [1][1].

The Straightforward Example

For A=[1,2,3]A = [1, 2, 3] the solution is 66. The subarray is [1,2,3][1, 2, 3].

The Tricky Example

For A=[1,2,3]A = [-1, -2, -3] the solution is 1-1. The subarray is [1][-1].

The Complex Example

For A=[1,3,6,2,4,3,6,3]A = [1, -3, 6, -2, 4, -3, -6, 3] the solution is 88. The subarray is [6,2,4][6, -2, 4].

The Example With a Catch

For A=[1,2,0,6,2]A = [1, -2, 0, 6, -2] the solution is 66. The subarray is [0,6][0, 6] or [6][6].

Another Perspective

We can look at this problem from a less abstract perspective. The given array can be interpreted as differences in price of a product in some time frame. For example, A=[1,3,0,6]A = [1, -3, 0, 6] could mean that a video game’s price increased by $1 on the first day, decreased by $3 on the second day, stayed the same on the third day, and increased by $6 on the last day.

Solving the maximum subarray problem is equivalent to finding a period of time with the highest increase of price. If an algorithm returns a sum for the subarray starting at index ii and ending at index jj, then you would get the most profit if you bought the game on day ii and sold it on day jj. Buy low, sell high.

Unfortunately, the answer is useless if you really seek the largest profit, unless you have a time machine or can somehow predict the prices before they happen. Nevertheless, it might be easier to think about the problem by looking at it this way.

The maximum subarray problem for an array [1,3,6,2,4,3,6,3][1,-3,6,-2,4,-3,-6,3] visualized on a graph. The solution for this array is 88, the subarray is [6,2,4][6,-2,4]. Imagine that this is a graph of prices of a product, which was shifted so that the initial price is 00 and the product was released on day 1-1. On day 00, the price increased by 11. On day 11, the price decreased by 33. And so on. You will obtain the largest profit of 88 if you buy on day 11 and sell on day 44.

Solutions

Brute Force

The Idea

Iterate over every possible subarray. A subarray can be identified by a valid pair of indices (i,j)(i, j), where ii is the index where the subarray begins, and jj is the index where the subarray ends. For each possible pair of indices (i,j)(i, j), calculate the sum for the subarray A[i...j]A[i...j] and keep track of the largest sum.

"Visualization of the brute force method for a small array."

The Pseudocode

function maxSubarraySum (A, n) {
let maxSum = -Infinity
for (let i = 0; i < n; ++i) {
for (let j = i; j < n; ++j) {
maxSum = max(maxSum, sum(A, from = i, to = j))
}
}
return maxSum
}

The Complexity

Since there are O(n2)O(n^2) pairs of indices (subarrays) and calculating the sum takes Θ(n)\Theta(n) time, the worst-case time complexity of this approach is O(n3)O(n^3). The memory complexity is Θ(1)\Theta(1).

Brute Force: The Sequel

The Idea

We still iterate over every possible subarray, but in a different order. This time, identify a subarray by a pair (,i)(\ell, i) where \ell is the length of the subarray and ii is the index at which the subarray ends.

"Visualization of the second brute force method for a small array."

The Pseudocode

function maxSubarraySum (A, n) {
let maxSum = -Infinity
for (let l = 1; l <= n; ++l) {
for (let i = l - 1; i < n; ++i) {
maxSum = max(maxSum, sum(A, from = i - l + 1, to = i]))
}
}
return maxSum
}

The Complexity

Since only the order in which we traverse all the possible subarrays changed, the worst-case time and memory complexity are the same.

The Why Is It Better Than the First

This change of order allows for an optimization to reduce the worst-case time complexity.

Sliding Window

The Idea

The previous method can be optimized by realizing that subarrays next to each other barely change. They only differ by two elements: the first element is removed from the current subarray and a new element is pushed back to it. This means the subarray sum also barely changes between the two subarrays. We can update the current subarray sum with only two operations: subtraction of the first element and addition of the next element. You can imagine that we’re “sliding” a “window” of size \ell along the whole array.

There is still one problem though. When we change the size of the subarray, the update is no longer that simple unless we “slide the other way” every other loop. We would have to consider two cases: going forward and going backward, pushing back and pushing front. It would work but the code probably wouldn’t be pretty.

Notice that the first subarray, starting from index 00, also barely changes when we increase its size. Only one element is pushed back into the subarray. Only one value is added to the first subarray sum. We can track the sum in a separate variable and update it only when the size changes.

"Visualization of the sliding window method for a small array."

The Pseudocode

function maxSubarraySum (A, n) {
let maxSum = -Infinity
let currentInitialSum = 0
let currentSum = 0
for (let l = 1; l <= n; ++l) {
currentInitialSum += A[l - 1]
currentSum = currentInitialSum
maxSum = max(maxSum, currentSum)
for (let i = l; i < n; ++i) {
currentSum -= A[i - l]
currentSum += A[i]
maxSum = max(maxSum, currentSum)
}
}
return maxSum
}

The Complexity

This method essentially got rid of the call to the Θ(n)\Theta(n) sum function and replaced it with a constant number of Θ(1)\Theta(1) operations per loop. This reduced the overall worst-case time complexity to O(n2)O(n^2) while keeping the memory complexity constant.

Dynamic Programming

The Greatest Lower Bound

Can we do better? A correct algorithm certainly needs to traverse the whole array at least once because the largest sum could be the sum of all the elements of the array and it cannot be calculated without knowing all the elements. So the greatest lower worst-case time bound seems to be Ω(n)\Omega(n). Can we achieve it?

Ideally, we would like to visit each element of the array at most once (or at least a constant number of times). We’ve already managed to reduce the worst-case time complexity by changing the order of subarrays in a way which allowed us to base each subarray on the previous one, at least for a constant size or for a constant index. What about changing the size and the index at the same time?

The Definition Pulled Out of a Hat

Let S(i)S(i) be the largest subarray sum for subarrays which end at index ii. Formally, we can define it as

S(i)=max{S(0,i),S(1,i),,S(i,i)},S(i) = \max\{S(0,i), S(1,i), \ldots, S(i, i)\},

where S(i,j)S(i,j) is the subarray sum for the subarray beginning at ii and ending at jj.

The Reason for the Definition Pulled Out of a Hat

We once again changed the order of subarrays. We choose an ending index first and then consider every possible size of the subarray, this time all at once. The answer to the problem is

max0i<nS(i).\max_{0 \le i < n} S(i).

"Visualization of the dynamic programming method for a small array."

The Calculations

Now, we need to figure out how to calculate S(i)S(i) quickly, based on the previous results. Let’s consider the base case first.

S(0)=A[0],S(0) = A[0],

assuming AA is not empty. Remember from the definition of S(i)S(i) that the last element is always included, no matter what, so there is really no choice here.

Now, let’s assume that we magically know the value of S(0)S(0), S(1)S(1), \ldots, and S(i1)S(i-1) for some i>0i > 0. How do we get S(i)S(i)? We must use A[i]A[i] in the sum so it’s a matter of choosing whether we want to use a previous subarray or not. In fact, we can only use S(i1)S(i-1), not S(i2)S(i-2) or any other S(ik)S(i-k). We can’t include A[i]A[i] in the other subarrays because we would break the subarray contiguity rule. Only two cases are left. We either add S(i1)S(i-1) to A[i]A[i] or not. Let’s choose the most profitable case.

Case 1

If adding S(i1)S(i-1) to A[i]A[i] gives us a larger sum than A[i]A[i], then we have no reason not to take S(i1)S(i-1). This can only happen when S(i1)S(i-1) is positive. That is

S(i1)+A[i]A[i]    S(i1)0.S(i-1) + A[i] \ge A[i] \iff S(i-1) \ge 0.

This inequality includes the case when S(i1)S(i-1) is 00. We take it also in this case because it doesn’t hurt the sum but it increases the size of the subarray, giving it potential to achieve even a larger sum later on.

Case 2

If taking S(i1)S(i-1) would result in a smaller sum, then it’s better to start clean. Take the subarray [A[i]][A[i]] and break the contiguity (we have to). This can only happen when S(i1)S(i-1) is negative, that is

S(i1)+A[i]<A[i]    S(i1)<0.S(i-1) + A[i] < A[i] \iff S(i-1) < 0.

The Equation

We can describe the logic with one equation.

S(i)=max(S(i1),0)+A[i].S(i) = \max(S(i-1), 0) + A[i].

The two cases are cleverly hidden behind the max\max expression.

The Pseudocode

function maxSubarraySum (A, n) {
let globalMaxSum = -Infinity
let currentMaxSum = -Infinity
for (let i = 0; i < n; ++i) {
currentMaxSum = Math.max(currentMaxSum, 0) + A[i]
globalMaxSum = Math.max(globalMaxSum, currentMaxSum)
}
return globalMaxSum
}

The Complexity

We have achieved the best possible worst-case time complexity which is Θ(n)\Theta(n), since we traverse the array only once, and every operation inside and outside the loop is Θ(1)\Theta(1). Only three variables are used, hence the memory complexity is Θ(1)\Theta(1).

The Equation From Another Perspective

Perhaps it will be easier to think about if you look at it from a different perspective. S(i1)S(i-1) is the maximum profit you can get by buying at some earlier point in time and selling on day i1i-1. If the profit is positive and you decide for some unknown reason that instead of selling the game on day i1i-1 you want to sell it on day ii, then you still get greater profit than if you’d bought it on day ii. On the other hand, if your “profit” is negative then it got really bad and it makes more sense to buy on day ii and hope that the price will rise tomorrow.

The Proof

The equation can also be derived mathematically straight from the definition of S(i)S(i). Consider S(i+1)S(i+1).

S(i+1)=max{S(0,i+1),S(1,i+1),,S(i,i+1),S(i+1,i+1)}S(i+1) = \max\{S(0,i+1), S(1,i+1), \ldots, S(i, i+1), S(i+1,i+1)\}

From the definition of S(i,j)S(i,j), we have S(i,j+1)=S(i,j)+A[j+1]S(i,j+1) = S(i,j) + A[j+1]. Hence

S(i+1)=max{S(0,i)+A[i+1],S(1,i)+A[i+1],,S(i,i)+A[i+1],S(i+1,i)+A[i+1]}.S(i+1) = \max\{S(0,i) + A[i+1], S(1,i) + A[i+1], \ldots, S(i, i) + A[i+1], S(i+1,i) + A[i+1]\}.

What is S(i+1,i)S(i+1,i)? It is 00, because subarray starting at i+1i+1 and ending at ii is an empty subarray. So

S(i+1)=max{S(0,i)+A[i+1],S(1,i)+A[i+1],,S(i,i)+A[i+1],A[i+1]}.S(i+1) = \max\{S(0,i) + A[i+1], S(1,i) + A[i+1], \ldots, S(i, i) + A[i+1], A[i+1]\}.

Now, for any constant cc and values a1,a2,,ana_1, a_2, \ldots, a_n it is true that

max{a1+c,a2+c,,an+c}=max{a1,a2,,an}+c.\max\{a_1 + c, a_2 + c, \ldots, a_n + c\} = \max\{a_1, a_2, \ldots, a_n\} + c.

Therefore

S(i+1)=max{S(0,i),S(1,i),,S(i,i),0}+A[i+1].S(i+1) = \max\{S(0,i), S(1,i), \ldots, S(i, i), 0\} + A[i+1].

It is also true that

max{a1,a2,,an,an+1}=max{max{a1,a2,,an},an+1}.\max\{a_1, a_2, \ldots, a_n, a_{n+1}\} = \max\{ \max\{a_1, a_2, \ldots, a_n\}, a_{n+1}\}.

And so finally

S(i+1)=max{max{S(0,i),S(1,i),,S(i,i)},0}+A[i+1],S(i+1) = \max\{ \max\{S(0,i), S(1,i), \ldots, S(i, i)\}, 0\} + A[i+1],

S(i+1)=max{S(i),0}+A[i+1].S(i+1) = \max\{S(i), 0\} + A[i+1]. \quad \blacksquare