[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