in reply to Largest Sum of Consecutive Integers
The sum of a contiguous subset is the total sum minus the sum of the left-side items that are left out and minus the sum of the right-side items that are left out. So instead of looking at O(N*N) combinations you can look at O(N) left-side possibilities and O(N) right-side possibilities and get the best answer. If an end-sum is not negative, then there is no benefit in omitting those items so only consider removing an end-run of items if it has a negative sum and the lowest sum of the end-runs.
But then you've got to deal with the special cases when this doesn't work. They aren't terribly tough to figure out but they certainly complicate the code. The trick is realizing these cases, but you'll probably hit them if you consider lists where most (or all) of the numbers are negative.
Update: But I haven't proven this to be correct, so there may be cases I haven't considered.
- tye
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: Largest Sum of Consecutive Integers (means)
by tye (Sage) on Aug 30, 2006 at 19:09 UTC | |
by OverlordQ (Hermit) on Aug 30, 2006 at 23:17 UTC |