[buug] substring of integers problem

[Karen Hogoboom]

I am unemployed, so I was trying networking to get a job, but since I had
applied to NSA and just recently to CIA, LBL and a few other places for a
job, things are apparently being counterfeited...just remind me what to
bring on Thursday.  I plan to be there.

On Thu, Feb 10, 2011 at 11:46 PM, Ian Zimmerman <itz at buug.org> wrote:

>
> Karen> Oh.  O.k.  Hmm.  And you don't think it's NP-Complete...if not
> Karen> then dynamic programming will probably solve it, but I would have
> Karen> to think awhile, maybe a long while, to figure out how.
>
> Ian> My solution is O(n log n) where n is the size of the input - I
> Ian> didn't do a formal proof, but it's clear from the structure of it
> Ian> and I did run huge randomized tests with multiple input sizes which
> Ian> confirmed it.
>
> Gee, I just got a book and it says:
>
> "The maximum segment sum problem enjoyed a burst of popularity at the
> end of the 1980s, mostly as a showcase for programmers to illustrate
> their favourite [sic!] style of program development or their particular
> theorem prover."
>
> This book doesn't give the solution, but it refers to Bentley's
> Programming Pearls which presumably does.
>
> --
> Ian Zimmerman <itz at buug.org>
> gpg public key: 1024D/C6FF61AD
> fingerprint: 66DC D68F 5C1B 4D71 2EE5  BD03 8A00 786C C6FF 61AD
> Ham is for reading, not for eating.
>



-- 
Karen L. Hogoboom

http://www.linkedin.com/in/karenlhogoboom
http://www.facebook.com/klhogoboom
http://boomtownbits.livejournal.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://buug.org/pipermail/buug/attachments/20110211/59a87a80/attachment.html>