python - 如何更快地求和范围值

Question

问题描述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.

问题并不像看起来那么微不足道，因为超时 - 测试列表太长:

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

我尝试了一些解决方案，到目前为止，最快的解决方案是:(用 timeit 检查，sum() 比循环更快并添加到结果中，如果我是对的？)

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

无论如何，对于极长的列表来说，这个速度不够快(最多 12 秒)。

我猜列表切片(每次创建新列表？)和每次迭代中的求和是瓶颈。 如何进一步优化代码，或者我必须完全改变方法？ 我希望提示，不是完整的解决方案。

Answer 1

累积总和可能就是您正在寻找的，应该很快，因为您只求和一次，然后减去。

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

编辑: 如果不允许 numpy 您可以自己计算 cumsum，例如使用

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