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: "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)?
Solutions to follow in additional TidBits.