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