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.