How to sum values of ranges faster

user_2045185 0
Viewed 333

Problem is described here

Given a list of integers A, for each pair of integers (first, last) in list ranges, calculate the sum of the values in A between indices first and last (both inclusive), and return the greatest resulting sum.

Problem is not so trivial as it seems, because of the timeout - test lists are way too long:

each integers-list : 100000 elements each ranges-list : 10000 elements

I have tried some solutions, and the fastest one, so far, was this: (checked with timeit, sum() is faster than loops and adding to the result, if i am right?)

def max_sum4(l, r):
    maxi = -1000000
    for el in r:
        if el[1] == len(l)-1:
            n=sum(l[el[0]:])
        else:
            n=sum(l[ el[0]: el[1]+1 ])
        if n>maxi:
            maxi=n
        
    
    return maxi
    #timeout, fastest one

Anyway, this one is not fast enough (max 12s) for the extremely long lists.

I guess that list slicing (new list created every time?) and summing in every iteration is bottleneck. How to optimize code further, or i have to change approach, completely? I would appreciate HINT, NOT complete solution.

python-3.x algorithm python performance
2 Answers

Cumulative sum is probably what you are looking for, should be fast, since you sum just once and then just subtract.

import numpy as np

def max_sum(a, ranges):
    maxi = -np.inf
    cs = np.cumsum(a)
    for el in ranges:
        val = cs[el[1]] - (cs[el[0]-1] if el[0] > 0 else 0)
        if val > maxi:
            maxi = val
    return maxi

EDIT: if numpy is not allowed you can calculate cumsum by yourself for example with

cs = [a[0]]
for i in range(1, len(a)):
    cs.append(cs[i-1] + a[i])
user_110831360

Try:

def max_sum(A, ranges):
     sums = []
     for start, end in ranges:
         sums.append(sum(A[start:end+1]))
     return max(sums)

Let me know if this is still too slow, it passes all their tests

user_78299630
Related