# Needed: A Simple Algorithm (Solution 1)

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

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

Answers:

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.