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.]
Max = 0.00 for Begin = 1 to N for End = Begin to N Sum = 0.0 for Index = Begin to End Sum = Sum + X[Index] Max = maximum(Max, Sum)
A) Prove this is a correct algorithm
B) How does the execution time vary with N?
C) What if it is known all elements of the vector are non-negative or non-positive?
A) Left to the reader.
B) It is Order(N**3) so if N = 1,000 requires an hour then N = 10,000 takes 39 days.
C) If all non-negative then the max is the sum of entire vector; if non-positive then the max is 0.0. Prove this.
Can you come up with solutions of Order (N**2) or even better Order(N Log(N)) or even better still Order(N)?
Solutions to follow in additional TidBits.