Суммы частей 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

Answer 2

Здесь мне нужно дважды перевернуть список, возможно, это 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]

 

Answer 3

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]

Answer 4

def parts_sums(ls):
    if len(ls) == 0: return [0]
    ret = [sum(ls)]
    ret.extend(parts_sums(ls[1:]))
    return ret