# 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=[-3,6,2,-1,7,3,-8,4,-1]$. The largest subarray is $[6,2,-1,7,3]$ 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}}(2+\underset{k=i}{\overset{j}{\Sigma}}1)$
- $=\frac{n(n-1)(n+7)}{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}}(1+\underset{j=i}{\overset{n}{\Sigma}}2)$
- $={n}^{2}$

To further improve performance we need two key observations:

- 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]$.
- 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.

Algorithm (Kadane).

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.

Proposition. Kadane’s algorithm is correct.

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[1\dots k-1]$ and $S$ is the max sum ending at $k-1$. We must show $S\prime =max(S+A\left[k\right],A\left[k\right])$ and that $M\prime =max(M,S\prime )$ for $k$.

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

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

This is a contradiction. Where $j<k$:

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

Since $T-A\left[k\right]$ is the sum associated with $A[j\dots k-1]$ 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<k$ 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$