Needed: A Simple Algorithm (Solution 3)

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 3:

Note: "To solve a problem of size N, recursively solve two problems of size approximately N/2, and combine their solutions to yield a solution to the complete problem."

So ... divide vector X into two vectors, A and B, of roughly equal size and find the maximum for each new vector and then consider the case where the maximum subvector of X overlaps the boundary between A and B.

recursive function MaxFromSpan(Begin, End)
if Begin > End
return 0.0 // error situation
if Begin == End
return maximum(0.0, X[Begin]
Middle = (Begin + End) / 2
// Find max vector that spans boundary between A & B
Sum = 0.0
MaxEndOfA = 0.0
for Index = Middle down to Begin
Sum += X[Index]
MaxEndOfA = maximum(Sum, MaxEndOfA)
Sum = 0.0
MaxBeginOfB = 0.0
for Index = Middle + 1 to End
Sum += X[Index]
MaxBeginOfB = maximum(Sum, MaxBeginOfB)
MaxOverlap = MaxEndOfA + MaxBeginOfB
MaxInA = MaxFromSpan(Begin, Middle)
MaxInB = MaxFromSpan(Middle + 1, End)
return maximum(MaxInA, MaxInB, MaxOverlap)
Max = MaxFromSpan(1, N)

A) Prove this is a correct algorithm

B) Prove it is Order(N Log(n)).

The basic trick to reduce from Order(N**2) in previous TibBits for Solution 1 to Order(N Log(N))) is to divide and recursively conquer.

Can you come up with a solution of Order(N)?