[buug] substring of integers problem
Karen Hogoboom
khogoboom at gmail.com
Sat Feb 5 08:53:10 PST 2011
Oh. O.k. Hmm. And you don't think it's NP-Complete...if not then dynamic
programming will probably solve it, but I would have to think awhile, maybe
a long while, to figure out how.
On Fri, Feb 4, 2011 at 10:04 PM, Ian Zimmerman <itz at buug.org> wrote:
>
> Karen> You may find this helpful:
> Karen> http://en.wikipedia.org/wiki/Longest_common_substring_problem
>
> That's an interesting problem too, but I don't think it is relevant to
> mine :-P I must have not explained it clearly, so I'll do it again
> here. Apologies to those who have already seen this.
>
> The problem is: given a list (array, finite sequence, vector - whatever
> you want to call it) of integers, positive and negative, find a slice
> (contiguous subsequence) which maximizes the *sum* of the integers in
> the slice.
>
> Examples: if the input list is [1, 2, 3, -8, 5], then there's exactly one
> solution, namely [1, 2, 3]. If the input list is [1, 2, 3, -8, 5, 8]
> there's again a unique solution, [5, 8]. If I change the -8 to a -6,
> there are now 2 solutions: [5, 8] and the full input list. Only one
> solution is required if there are multiple ones.
>
> --
> 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/20110205/b1c758a5/attachment.html>
More information about the buug
mailing list