# Needed: A Simple Algorithm (Solution 2)

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 2a:

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?

Answers:

B) It is Order(N**2) so if N = 1,000 requires an hour then N =
10,000 takes 4 days.

## Solution 2b:

Notice that sum X[Begin .. End] is CumArray[End] - CumArray[Begin
- 1]

`CumArray[0] = 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.