[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