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)?

Bruteforce

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 Θ(n3).

Optimized bruteforce

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 k1 is S, then the sum of the subarray from i to k is simply S+A[k].

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 Θ(n2).

Kadane’s algorithm

To further improve performance we need two key observations:

  1. Let S be the max sum ending at k1. The max sum ending at k is the greater of S+A[k] and A[k].
  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.

Algorithm.

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[1]. Assume for k1 we know M is max sum for A[1k1] and S is the max sum ending at k1. We must show S=max(S+A[k],A[k]) and that M=max(M,S) for k.

We prove induction holds on S by way of contradiction. Assume there exists subarray A[jk] whose sum T>S. Where j=k:

This is a contradiction. Where j<k:

Since TA[k] is the sum associated with A[jk1] this violates our inductive hypothesis, namely that S is the max sum ending at k1.

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 be the greater of the two assures this.

Complexity. This approach is asymptotically Θ(n).