Needed: A Simple Algorithm (Solution 4)

The Problem: "The input is a vector X of N real numbers; the output is the maximum sum found in any contiguous subvector of the input." A zero length subvector has maximum 0.0.

[From Programming Pearls by Jon Bentley.]

Solution 4:

Note: Scan from 1 to N keeping track of maximum subvector seen so far, MaxSoFar. Knowing solution for X[1 .. (Index - 1)] use a divide and conquer technique to extend to a solution for X[1 .. Index]. Either the maximum for [1 .. Index] is the maximum for [1 .. (Index -1)] which is MaxSoFar or it is a vector that ends with X[Index] and extends back towards to X[1] which we call MaxHere. The trick to avoiding an Order(N**2) solution is to be tricky about calculating the MaxHere.

MaxSoFar = 0.0
MaxHere  = 0.0
for Index = Begin to N
   // Invariant: MaxSoFar and MaxHere are correct for
   // X[1 .. (Index - 1)]
   // This is the tricky part: Can you prove why this works?
   MaxHere = maximum(MaxHere + X[Index], 0.0)
   // Then the usual
   MaxSoFar = maximum(MaxSoFar, MaxHere)
Max = MaxSoFar

A) Prove this is a correct algorithm

B) Prove it is Order(N).

See next TidBits for a comparison for the four solutions that were of Order N**3, N**2, N*Log(N) and N and why the Order of an algorithm can be important.