# Maximum Subarray Problem

Given a one-dimensional array of numbers, find the contiguous subarray with the largest sum. For the purposes of this analysis we will exclude empty subarrays.

Let $A$ be an array such that $A=\left[-3,6,2,-1,7,3,-8,4,-1\right]$. The largest subarray is $\left[6,2,-1,7,3\right]$ with a sum of $17$.

How can we compute this? How fast can we do this (counting assignments)?

The most obvious approach is to generate all possible subarrays and compute their max sum. Let $M$ be the max sum seen so far, $i$ and $j$ the start and end indices of the current subarray, and $S$ be the sum of the current subarray.

Algorithm.

```M = A[1] for i = 2 to n do for j = i to n do S = 0 for k = i to j do S = S + A[k] M = max(M, S)```

Complexity. This approach is asymtotically $\Theta \left({n}^{3}\right)$.

• $1+\underset{i=2}{\overset{n}{\Sigma }}\underset{j=i}{\overset{n}{\Sigma }}\left(2+\underset{k=i}{\overset{j}{\Sigma }}1\right)$
• $=\frac{n\left(n-1\right)\left(n+7\right)}{6}+1$

We can easily optimize the bruteforce algorithm if we realize that recomputing the sum of a subarray every time is wasteful. If we know the sum of the subarray from $i$ to $k-1$ is $S$, then the sum of the subarray from $i$ to $k$ is simply $S+A\left[k\right]$.

Algorithm.

```M = A[1] for i = 2 to n do S = 0 for j = i to n do S = S + A[j] M = max(M, S)```

Complexity. This approach is asymtotically $\Theta \left({n}^{2}\right)$.

• $1+\underset{i=2}{\overset{n}{\Sigma }}\left(1+\underset{j=i}{\overset{n}{\Sigma }}2\right)$
• $={n}^{2}$

To further improve performance we need two key observations:

1. Let $S$ be the max sum ending at $k-1$. The max sum ending at $k$ is the greater of $S+A\left[k\right]$ and $A\left[k\right]$.
2. Let $L$ be the set of the max sums ending at each index in $A$. The largest element in $L$ is our answer.

Kadane’s algorithm uses these two observations to compute the max sum in linear time.

```S = A[1], M = A[1] for i = 2 to n do S = max(S + A[i], A[i]) M = max(M, S)```

The correctness of Kadane’s algorithm may not be apparent. A proof may be necessary to clarify.

Proof. We prove by induction. For basis $k=1$, trivially the sums $S=M=A\left[1\right]$. Assume for $k-1$ we know $M$ is max sum for $A\left[1\dots k-1\right]$ and $S$ is the max sum ending at $k-1$. We must show $S\prime =max\left(S+A\left[k\right],A\left[k\right]\right)$ and that $M\prime =max\left(M,S\prime \right)$ for $k$.

We prove induction holds on $S$. Assume to the contrary there exists subarray $A\left[j\dots k\right]$ whose sum $T>S\prime$. Where $j=k$:

• $T>S\prime$
• $A\left[k\right]>max\left(S+A\left[k\right],A\left[k\right]\right)$
• $A\left[k\right]>A\left[k\right]$

This is a contradiction. Where $j:

• $T>S\prime$
• $T>max\left(S+A\left[k\right],A\left[k\right]\right)$
• $T-A\left[k\right]>S$

Since $T-A\left[k\right]$ is the sum associated with $A\left[j\dots k-1\right]$ this violates our inductive hypothesis, namely that $S$ is the max sum ending at $k-1$.

We prove induction holds on $M$ by cases. The subarray must end at some index $i$. If $i then we should use $M$, but if $i=k$ then we should use $S$. Letting $M\prime$ be the greater of the two assures this.

Complexity. This approach is asymptotically $\Theta \left(n\right)$.

• $2+\underset{i=2}{\overset{n}{\Sigma }}2$
• $=2n$