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:24 pm

* 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?

-- 
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?

.