# Needed: A Simple Algorithm (Solution 4)

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

Note: Scan from 1 to N keeping track of maximum subvector seen
so far, MaxSoFar. Knowing solution for X[1 .. (Index - 1)] use
a divide and conquer technique to extend to a solution for X[1
.. Index]. Either the maximum for [1 .. Index] is the maximum
for [1 .. (Index -1)] which is MaxSoFar or it is a vector that
ends with X[Index] and extends back towards to X[1] which we call
MaxHere. The trick to avoiding an Order(N**2) solution is to be
tricky about calculating the MaxHere.

`MaxSoFar = 0.0
MaxHere = 0.0
for Index = Begin to N
// Invariant: MaxSoFar and MaxHere are correct for
// X[1 .. (Index - 1)]
// This is the tricky part: Can you prove why this works?
MaxHere = maximum(MaxHere + X[Index], 0.0)
// Then the usual
MaxSoFar = maximum(MaxSoFar, MaxHere)
Max = MaxSoFar`

A) Prove this is a correct algorithm

B) Prove it is Order(N).

See next TidBits for a comparison for the four solutions that
were of Order N**3, N**2, N*Log(N) and N and why the Order of
an algorithm can be important.