Name that algorithm (a small puzzle)

[Charles Fineman]

) A friend showed me a interestng problem the other day. In light of
) the interest in the 2^n celing problem a couple of months ago, I 
) thought y'all might be interested...
) 
)     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. 
) 
) I will post my solution in a few days if there is sufficient interest.
) 
) 	Charlie Fineman
) 
Ooops... The above formulation seemed to cause problems locally so I'm 
posting a clarification (some people are so _literal_ :-). We are
looking for the maximal sub-STRING that is a maximal subsequence whose
terms are continguous in the original sequence.

One other point... There are two possible ways to look at the problem
(both are perfectly acceptable interpretations, the code will be almost 
identical). 

Some solutions return the empty string if there are no positive terms 
in the sequence. This is certainly valid (as the empty sumantion is 
defined to be zero which is greater than an negative number).

One could also write the algorithm to return the maximal NON-EMPTY
sub-string. 
--