[buug] substring of integers problem

Ian Zimmerman itz at buug.org
Thu Feb 10 23:46:11 PST 2011


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.



More information about the buug mailing list