Skip to content
Advertisement

loop through the list to get Maximum sum for a given range in python

I am a novice in python. I have a code where I loop through a list to capture maximum sum of numbers for given range k. It is working fine but I want it to make it shorter/optimal. ‘k’ may vary

numb = [100,33,22,200,333,1000,22]
m=0
k=2
sum1=0
temp=[]
for j in range(len(numb)-(k-1)):
   for i in range(m,k):
     temp.append(numb[i])
   if sum1 < sum(temp):
     sum1 = sum(temp)
   temp=[]
   m+=1
   k+=1
print(sum1)

Ans: 1533 when k = 3 Ans: 1333 when k = 2

Advertisement

Answer

You can start by adding up the first k numbers. That is your starting sum and your current max. Then run a sliding window along the list, adding the next number and removing the one that goes out of the window.

def sum_k(x, k):
    m = s = sum(x[:k])
    for i, a in enumerate(x[k:]):
        b = x[i]  # number to remove
        s += a - b
        m = max(m, s)
    return m


numb = [100, 33, 22, 200, 333, 1000, 22]
print(sum_k(numb, 2), sum_k(numb, 3))

This runs in linear time, which is optimal since you need to at least look at every element in your input.

The index, i, in the loop runs from zero to n-k-1, so although we enumerate over x[k:] the indices we pick are from x[0:], so when we pick b we are picking the number that goes out of the window. Meanwhile, a is the new number that comes in.

User contributions licensed under: CC BY-SA
9 People found this is helpful
Advertisement