I am new to the competitive programming. I am finding trouble in doing the following problem.

The question is that you have given an array or list. And a number M, now you hav to find the continuous subarray of size M having the largest sum.

For example if list is 4,6,10,8,2,1 and M=3 then largest sum window will be 6,8,10 that is sum equal 24 . So answer will be 24

Can anyone help me regarding this question?

CodePudding user response：

You can edit the list and remove the largest number successively:

list = [4,6,10,8,2,1]
M = 3
result = 0
# to get unique elements
new_list = set(list)

for i in range(M):
   result  = max(new_list)
   # removing the largest element from new_list
   new_list.remove(max(new_list))

print(result)

CodePudding user response：

l=[4,6,10,8,2,1]
ans=0
m=3
for i in range(len(l) 1):
   for j in range(i):
       if len(l[j:i])==m:
          ans=max(ans,sum(l[j:i]))
print(ans)  

find the sublist of list and store sum of sublist in variable

CodePudding user response：

1. First think of a brute force solution. Here it is simple we can find the answer using two for loops(nested). Outer loop will mark as starting point and inner loop will go to next M elements.
2. Now comes the hard part i.e., optimization. Since it is a continuous subarray of fixed size you can make window of fixed size(here M) using two pointer(say left and right) and maintain the size of the window and keep moving towards right and keep calculating the sum and updating the ans if required.

    sum = 0
    for i in range(M):
        sum = arr[i]
 
    ans = sum
    for i in range(M, len(arr)):
        sum  = arr[i] - arr[i-M]
        ans = max(res, sum)
 
    return ans

3. Of course, we have to check for some corner cases like if M is greater than size of array or M=0

CodePudding user response：

I tried this solution:

l = [4,6,1,8,2,1]
M = 3

largest_sum = -1
output = []
# Getting all possible sequences of M numbers
for i in range(len(l)):
    if (res:=sum(l[i:i 3])) > largest_sum:
        largest_sum = res
        output = l[i:i 3]

print(f"Largest sum is {largest_sum} from array {output}")

Output:

Largest sum is 15 from array [6, 1, 8]

It might not be the most efficient algorithm, but it works. I get all possible sequences o length M and store the largest sum.

Note: it works with @zeeshan12396 case too.