[buug] substring of integers problem

Ian Zimmerman itz at buug.org
Fri Feb 4 22:04:20 PST 2011


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.



More information about the buug mailing list