[buug] substring of integers problem

[Michael Paoli]

Ah, yes, ...
http://en.wikipedia.org/wiki/Maximum_subarray_problem
has an additional constraint:
"containing at least one positive number"
which I didn't include, as it's not stated/included in:
http://www.weak.org/pipermail/buug/2011-February/003716.html

It was a "simple enough" problem there was likely much material (and
"solutions") on it ... but for purpose of exercise, I didn't peek.  I
was somewhat surprised how the algorithm got simpler and simpler as I
optimized (and fixed) the code.

$ ./maxsumsubset -5 -3 -5
-3
$

references/excerpts:
http://www.weak.org/pipermail/buug/2011-March/003741.html

> From: "Ian Zimmerman" <itz at buug.org>
> Subject: Re: [buug] substring of integers problem
> Date: Sat, 12 Mar 2011 22:59:51 -0800

> Michael> Not quite a "perfect" solution (e.g. it can hit some
> Michael> overflow/underflow/conversion errors in some cases - including
> Michael> not detecting them in some cases), but ...  I also realized
> Michael> later I could've coded it to solve from left to right, rather
> Michael> than right to left ... and could thus possibly not
> Michael> process/parse the arguments (input integers) until they're
> Michael> needed, and thus also not need to store them all.  Most of the
> Michael> "real work" happens within about 21 lines of body of loop.  The
> Michael> rest is mostly just initialization and final output.  It needs
> Michael> more comments :-) ... I had a bunch, but stripped most of them
> Michael> out ... they'd not kept up to how the code had "evolved".
>
> Yes, I think that's correct (allowing for my rusty Perl).
>
> I found that this is quite a famous problem, it's discussed in 2 books I
> got this month :-)  It's also in wikipedia:
>
> https://secure.wikimedia.org/wikipedia/en/wiki/Maximum_subarray_problem