What is an elegant way of finding the max value produced by a running sum?

Question

I have some data, for example a log of changes in number of magic beans in my possession. To simplify the question, assume it's already sorted by date (from old to new) and can be represented by this list:

a = [1,2,3,-4,5,-6]

notice each number means the change in number of magic beans, not the current total. So, I start with 1 bean, then I get 2 more, then I get 3 more, then I give away 4 beans to someone, etc.

What I want to find is the max number of beans I have ever had in my possession at a single point in time. That is to say, what is the most beans I've ever had in my pockets.

To do this, I wrote this code:

a = [1,2,3,-4,5,-6]

def find_max_seats(some_list):
    running_list = []
    running_sum = 0
    for i in some_list:
        running_sum += i
        running_list.append(running_sum)
    return max(running_list)


print find_max_seats(a)

It works (the answer is 7), but there has to be a more elegant and pythonic way to do that.

Thanks for your help!

@200OK I don't understand... I already use max in my solution — Optimesh, Jun 25 '14 at 09:07
The solutions there are using `list()` or list comprehension to generate the list with cumulative sums, since you only want the biggest item not all of them, so simply call `max()` there: `max(accumu(a))`. This will prevent creation of an unnecessary list. — Ashwini Chaudhary, Jun 25 '14 at 09:11

score 1 · Answer 1 · edited May 23 '17 at 12:20

1

This should work in Python 3:

from itertools import accumulate

def find_max_seats(some_list):
    return max(accumulate(some_list))

Unfortunately, the accumulate function is not in Python 2.7. You can define something similar as described in the question linked by 200 OK: How to find the cumulative sum of numbers in a list?

So, for example:

def accumulate(xs):
    total = 0
    for x in xs:
        total += x
        yield total

edited May 23 '17 at 12:20

Community

1
1

answered Jun 25 '14 at 08:53

Weeble

17,058
3
60
75

1

Question is tagged with Python 2.7. – Ashwini Chaudhary Jun 25 '14 at 08:53

What is an elegant way of finding the max value produced by a running sum?

1 Answers1