Subj : Re: question about finding sum of subset of contiguos elements of an array .
To   : comp.programming
From : Googmeister
Date : Thu Oct 06 2005 04:51 pm

maadhuu wrote:
> hello ,
> Given an array of positive and negative numbers, how do you come with an
> algorithm to find the subset of elements that have the highest sum .
>
> I can think of implementing an O(n^2) algorithm, but how do you do it in
> time less than that ??
> Thanking you,
> Yours sincerely
> Maadhuu

Go to the library and read Jon Bentley's "Programming Pearls."
It's entertaining and you'll learn a lot more than just how to
solve this problem in linear time.

.