让我们考虑这个例子(以通用格式编写的数组(：
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
这里有一个迭代的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
def parts_sums(ls):
if len(ls) == 0: return [0]
ret = [sum(ls)]
ret.extend(parts_sums(ls[1:]))
return ret
def fn(ls):
if len(ls)==0:
return [0]
return [sum(ls[i:len(ls)]) for i in range(len(ls))]
###################################
print(1,fn([0, 1, 3, 6, 10]))
print(2,fn([]))
输出将类似
1 [20, 20, 19, 16, 10]
2 [0]
这里我必须反转列表两次，也许是2*O(n)，除非res[-1]不会增加复杂性：
xs = [0,1,3,6,10]
def summed(xs):
res = [0]
for x in reversed(xs):
res.append(x+res[-1])
return reversed(res)
这应该表现得更好，O(n):
def summed2(xs):
res = [0]
for i, x in enumerate(reversed(xs)):
res = [x+res[0]] + res
return res
assert summed2(xs) == [20, 20, 19, 16, 10, 0]