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.]
Notice that the sum of X[i .. j] has a simple relationship to the sum of X[i .. (j-1)], namely just add X[j]
Max = 0.00 for Begin = 1 to N Sum = 0.0 for Index = Begin to N Sum = Sum + X[Index] // Sum now contains sum of X[Begin .. Index] Max = maximum(Max, Sum)
A) Prove this is a correct algorithm
B) How does the execution time vary with N?
B) It is Order(N**2) so if N = 1,000 requires an hour then N = 10,000 takes 4 days.
Notice that sum X[Begin .. End] is CumArray[End] - CumArray[Begin - 1]
CumArray = 0 for Index = 1 to N CumArray[Index] += X[Index] Max = 0.0 for Begin = 1 to N for End = Begin to N Sum = CumArray[End] - CumArray[Begin] Max = maximum(Max, Sum)
Prove that this algorithm is also Order(N**2).
The basic trick to reduce from Order(N**3) in previous TidBits for Solution 1 to Order(N**2) is to reuse information from loop to loop.
Can you come up with solutions of Order(N Log(N)) or even better still Order(N)?
Solutions to follow in additional TidBits.