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

* Alf P. Steinbach:
> * Willem:
> > Richard wrote:
> > ) Given the subject line it is almost certain that he means subset of
> > ) contiguous elements.  Shouldn't there be a limit to nit-picking?
> > 
> > Aww, lemme have a bit of fun with them CS-101 students. :-)
> > 
> > Anyway, one possible O(n) solution I can think of needs O(n) extra memory,
> > for an auxiliary array.  I can't think of a solution offhand that doesn't.
> > That doesn't mean there isn't one, of course, it just means it's been too
> > long since my days in CS class, and I have to use my big thumb instead. :)
> 
> I don't understand the problem.  Is it, find the contigous sequence of
> elements with highest sum?  Then just scan the array noting the end of a
> sequence when a negative number is encountered, and noting the start of a
> sequence when after a negative number, a non-negative number is encountered.
> If there are no non-empty such sequences, pick the first negative number that
> is of lowest absolute value.  But that can't be the problem, can it?

Ah, my bad.  If a positive number sequence sums to higher than the absolute
value sum of the preceding negative number sequence, or the succeeding one,
then that presents opportunities for coalescing the sequences.  OK, there's a
problem.

-- 
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

.