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)?

Solutions to follow in additional TidBits.