How can I optimize this code to handle large values?

I was working on a project, and I noticed that this for loop takes a very long time to run.

d = [0, 1, 2, 5, ..., 0, 0] # Max array size: 100000 (10^5)
for i in range(len(d)): 
  sums = sum(d[i:]) * (i + 1)
  if sums > max_sum:
    max_sum = sums
    max_idx = i + 1

Is there a way to optimize it so that it can handle large values like 10^5 as the value of len(d)?

Thanks!

>Solution :

Your code exhibits quadratic behavior because you are repeatedly recomputing the same sums in your loop: sum(d[i:]) == d[i] + sum(d[i+1:]).

Start by computing the sum of d[0:] == d, then subtract each item from that sum as you iterate.

subsum = sum(d)
for i, item in enumerate(d):
    sums = subsum * (i+1)
    subsum -= item
    if sums > max_sum:
        max_sum = sums
        max_idx = i + 1