python - Python 3 的部分总和

Question

让我们考虑这个例子(以通用格式编写的数组):

ls = [0, 1, 3, 6, 10]

它的以下部分:

ls = [0, 1, 3, 6, 10]
ls = [1, 3, 6, 10]
ls = [3, 6, 10]
ls = [6, 10]
ls = [10]
ls = []

相应的和是(放在一个列表中):[20, 20, 19, 16, 10, 0]

函数 parts_sums(或其在其他语言中的变体)将以列表 ls 作为参数，并返回如上定义的其各部分之和的列表。

我试过这样但是没有在给定的执行时间内执行。我怎样才能加速这段代码:

def parts_sums(ls):
    sums=[]
    if len(ls)==0:
        return[0]
    else:
        while len(ls)!=0:
            sums.append(sum(ls))
            ls.pop(0)
        sums.append(0)
        return sums

Answer 1

这是一个迭代的 O(n) 解决方案。

def parts_sums(ls):
    sums = [0] * (len(ls) + 1)
    for i, e in enumerate(reversed(ls)):
        sums[len(ls) - i - 1] += sums[len(ls) - i] + e
    return sums