# The Maximum Subarray Problem

## The Problem

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

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

## Examples

### The Pathological Example

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

### The Simplest Example

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

### The Straightforward Example

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

### The Tricky Example

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

### The Complex Example

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

### The Example With a Catch

For $A = [1, -2, 0, 6, -2]$ the solution is $6$. The subarray is $[0, 6]$ or $[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]$ 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 $i$ and ending at index $j$, then you would get the most profit if you bought the game on day $i$ and sold it on day $j$. 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.

## Solutions

### Brute Force

#### The Idea

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

#### 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(n^2)$ pairs of indices (subarrays) and calculating the sum takes $\Theta(n)$ time, the worst-case time complexity of this approach is $O(n^3)$. The memory complexity is $\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 $(\ell, i)$ where $\ell$ is the length of the subarray and $i$ is the index at which the subarray ends.

#### 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 $0$, 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.

#### 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 $\Theta(n)$ sum function and replaced it with a constant number of $\Theta(1)$ operations per loop. This reduced the overall worst-case time complexity to $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 $\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)$ be the largest subarray sum for subarrays which end at index $i$. Formally, we can define it as

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

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

#### 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

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

#### The Calculations

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

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

assuming $A$ is not empty. Remember from the definition of $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(1)$, $\ldots$, and $S(i-1)$ for some $i > 0$. How do we get $S(i)$? We must use $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(i-1)$, not $S(i-2)$ or any other $S(i-k)$. We can’t include $A[i]$ in the other subarrays because we would break the subarray contiguity rule. Only two cases are left. We either add $S(i-1)$ to $A[i]$ or not. Let’s choose the most profitable case.

##### Case 1

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

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

This inequality includes the case when $S(i-1)$ is $0$. 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(i-1)$ would result in a smaller sum, then it’s better to start clean. Take the subarray $[A[i]]$ and break the contiguity (we have to). This can only happen when $S(i-1)$ is negative, that is

$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(i-1), 0) + A[i].$

The two cases are cleverly hidden behind the $\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 $\Theta(n)$, since we traverse the array only once, and every operation inside and outside the loop is $\Theta(1)$. Only three variables are used, hence the memory complexity is $\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(i-1)$ is the maximum profit you can get by buying at some earlier point in time and selling on day $i-1$. If the profit is positive and you decide for some unknown reason that instead of selling the game on day $i-1$ you want to sell it on day $i$, then you still get greater profit than if you’d bought it on day $i$. On the other hand, if your “profit” is negative then it got really bad and it makes more sense to buy on day $i$ and hope that the price will rise tomorrow.

#### The Proof

The equation can also be derived mathematically straight from the definition of $S(i)$. Consider $S(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)$, we have $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], \ldots, S(i, i) + A[i+1], S(i+1,i) + A[i+1]\}.$

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

$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 $c$ and values $a_1, a_2, \ldots, a_n$ it is true that

$\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), \ldots, S(i, i), 0\} + A[i+1].$

It is also true that

$\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), \ldots, S(i, i)\}, 0\} + A[i+1],$

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