[buug] substring of integers problem

[Karen Hogoboom]

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>