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.<br><br><div class="gmail_quote">
On Fri, Feb 4, 2011 at 10:04 PM, Ian Zimmerman <span dir="ltr"><<a href="mailto:itz@buug.org">itz@buug.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<br>
Karen> You may find this helpful:<br>
Karen> <a href="http://en.wikipedia.org/wiki/Longest_common_substring_problem" target="_blank">http://en.wikipedia.org/wiki/Longest_common_substring_problem</a><br>
<br>
That's an interesting problem too, but I don't think it is relevant to<br>
mine :-P  I must have not explained it clearly, so I'll do it again<br>
here.  Apologies to those who have already seen this.<br>
<br>
The problem is:  given a list (array, finite sequence, vector - whatever<br>
you want to call it) of integers, positive and negative, find a slice<br>
(contiguous subsequence) which maximizes the *sum* of the integers in<br>
the slice.<br>
<br>
Examples: if the input list is [1, 2, 3, -8, 5], then there's exactly one<br>
solution, namely [1, 2, 3].  If the input list is [1, 2, 3, -8, 5, 8]<br>
there's again a unique solution, [5, 8].  If I change the -8 to a -6,<br>
there are now 2 solutions: [5, 8] and the full input list.  Only one<br>
solution is required if there are multiple ones.<br>
<font color="#888888"><br>
--<br>
Ian Zimmerman <<a href="mailto:itz@buug.org">itz@buug.org</a>><br>
gpg public key: 1024D/C6FF61AD<br>
fingerprint: 66DC D68F 5C1B 4D71 2EE5  BD03 8A00 786C C6FF 61AD<br>
Ham is for reading, not for eating.<br>
</font></blockquote></div><br><br clear="all"><br>-- <br>Karen L. Hogoboom<br><br><a href="http://www.linkedin.com/in/karenlhogoboom" target="_blank">http://www.linkedin.com/in/karenlhogoboom</a><br><a href="http://www.facebook.com/klhogoboom" target="_blank">http://www.facebook.com/klhogoboom</a><br>
<a href="http://boomtownbits.livejournal.com" target="_blank">http://boomtownbits.livejournal.com</a><br><br>