[Tim]
Woo hoo! Another coincidence. I just happened to be playing with this problem today:
You have a large list - xs - of N numbers. It's necessary to compute slice sums
sum(xs[i:j])
for a great many slices, 0 <= i <= j <= N.
Which brought to mind a different problem: we have a list of numbers, `xs`. For each index position `i`, we want to know the largest sum among all segments ending at xs[i], and the number of elements in a maximal-sum slice ending at xs[i]. `accumulate()` is a natural way to approach this, for someone with a functional language background. You'll have to trust me on that ;-) But there are some twists: - The identity element for max() is minus infinity, which accumulate() can';t know. - We want to generate a sequence of 2-tuples, despite that xs is a sequence of numbers. - In this case, we do _not_ want to see the special initial value. For example, given the input xs [-10, 3, -1, 7, -9, -7, -9, 7, 4] we want to generate (-10, 1), (3, 1), (2, 2), (9, 3), (0, 4), (-7, 1), (-9, 1), (7, 1), (11, 2) Note: the largest sum across all non-empty slices is then max(that_result)[0]. The code below could be easily changed to keep track off that incrementally too, but this is already so different from "plain old running sum" that I don't want more novelty than necessary to make the points (a special initial value is needed, and it's not necessarily insane to want to produce results of a different type than the inputs). The key part is the state updating function: def update(state, x): prevmax, count = state newsum = prevmax + x if newsum > x: return newsum, count + 1 else: return x, 1 That's all there is to it! Then, e.g.,
from itertools import accumulate, chain import math xs = [-10, 3, -1, 7, -9, -7, -9, 7, 4] initial = (-math.inf, 1) result = accumulate(chain([initial], xs), update) next(result) # discard unwanted value (-inf, 1) list(result) [(-10, 1), (3, 1), (2, 2), (9, 3), (0, 4), (-7, 1), (-9, 1), (7, 1), (11, 2)]