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
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.
This is the simplified code you want which takes O(n) of time complexity. This approach is based on Sliding Window Algorithm.
maxSum is the function which takes 2 arguments (array of numbers and k) and returns maximum for any value of k.
def maxSum(arr, k):
# Edge case
if len(arr) <= k:
return sum(arr)
sums = sum(arr[:k]) # sum the first 3 val in arr.
start = 0 # tell us the first element index whose value is in sums variable
maximum = sums
for val in arr[k:]:
sums = (sums - arr[start]) + val
# here we first subtracted the start value and then added current value.
# Eg. From [1,2,3,4] sums have 1+2+3, but now sums have ( 1+2+3(previous) - 1(start) ) + 4(current)
# Now check for maximum.
if sums > maximum:
maximum = sums
# now increase start by 1 to make pointer to value '2' and so on.
start += 1
# return maximum
return maximum
arr = [100,33,22,200,333,1000,22]
k = 2
print("For k=2: ", maxSum(arr, k))
k = 3
print("For k=3: ", maxSum(arr, k))
Output:
For k=2: 1333
For k=3: 1533
