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

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

CodePudding user response：

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.

CodePudding user response：

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=2:  1533