[buug] substring of integers problem

[Joseph Zitt]

I didn't see the original post, but for small cases, there's a simple
if inelegant solution.

If the arrays aren't too large and there aren't too many of them, it
might be worthwhile to use relative brute force on them with a Perl
script or something like it. Just add up each of the possible slices
in turn, and choose the one with the largest result. For the sample
set of five items, there are only fifteen possible slices (or ten, if
you don't allow slices of only one item).

But this seems sufficiently obvious that I'm probably making an
incorrect assumption about the actual size of the data being
processed.

On Sat, Feb 5, 2011 at 1:04 AM, 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.
> _______________________________________________
> Buug mailing list
> Buug at weak.org
> http://www.weak.org/mailman/listinfo/buug
>



-- 
Joseph Zitt ::http://www.josephzitt.com