Name that algorithm (a small puzzle)

[Mark Kornell]

In article <3968 at pt.cs.cmu.edu>, cef at h.gp.cs.cmu.edu (Charles Fineman) writes:
 >     Let a sequence of integers be given. Define a "maximal"
 >   sub-string to be a sub-string whose sum is the greatest
 >   of all sub-strings (there could be more than one).
 > 
 >     Find the cheapest (time-wise) algorithm that will find a
 >   "maximal" subsequence and return its range and sum. 
 > 
 > 	Charlie Fineman


Several algorithms to do this task were developed and compared in the CACM
column, "Programming Pearls", in Volume 27, Number 9 (Sept 84), pp. 865 - 
871.

The algorithms ranged from a cubic (on the length of the sequence) algorithm
to a linear algorithm.

The algorithms given only computed the sum of the maximum sub-range, and did
not return the range itself.  However, it would be trivial to keep track of
this information.

> The meek shall inherit the earth --  |    Mark Kornell                       <
>   in plots 6 feet by 3 feet          |       kornellm at cpsc.UCalgary.CA       <
>   (but they do get mineral rights)   |       Kornell at UNCAMULT                <
================================================================================