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

On Thu, 6 Oct 2005 18:21:50 +0000 (UTC), Willem <willem@stack.nl>
wrote:

>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 ??
>
>Just select all the positive numbers.  That should be the subset with
>the highest sum.  Or isn't that what you meant with subset ?

Given the subject line it is almost certain that he means subset of
contiguous elements.  Shouldn't there be a limit to nit-picking?


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
I started out in life with nothing.
I still have most of it left.

.