I have been learning Python for 2 months now. In order to hone my programming skills, I solve problems on Codewars from time to time.

Task

Codewars kata:

Write a program that takes a list of numbers as an argument and return a list of partial sums.

My Attempt

I wrote a solution that I tested and it works:

def parts_sums(ls):
    length=len(ls) 1
    def gen():
        for elt in range(0,length):
            yield sum(ls[elt:])   
    
    result= list(gen())
    return result

Codewars is rejecting this solution because it's too slow for lists with thousands of numbers.

I have spent an embarrassingly huge amount of time trying to come up with a faster solution with no avail.

How can the algorithm be designed more performant?

CodePudding user response：

A solution with an explicit loop:

result= ls   [0]
for i in range(len(result)-1, 0, -1):
  result[i-1]= result[i]   result[i-1]

Note that it can also be done in-place in ls.

CodePudding user response：

You don't have to compute the sum of a slice at each step, all you have to do is subtract one number from the previous sum.

Here's a pretty naive but straight forward solution, subject to further optimizations.

def part_sums(ls):
    result = [sum(ls)]
    for x in ls:
        result.append(result[-1] - x)
    return result