[buug] substring of integers problem
Michael.Paoli at cal.berkeley.edu
Sun Mar 13 10:25:05 PDT 2011
Ah, yes, ...
has an additional constraint:
"containing at least one positive number"
which I didn't include, as it's not stated/included in:
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
> 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:
More information about the buug