找到大小为 M 的最大连续子数组和

Question

我是竞争性编程的新手。我在做以下问题时遇到了麻烦。

问题是你给的是数组或者列表。和一个数M，现在你要找到具有最大和的大小为M的连续子数组。

例如，如果列表为 4,6,10,8,2,1 且 M=3，则最大和 window 将为 6,8,10，即和等于 24。所以答案将是 24

谁能帮我解决这个问题？

Answer 1

您可以编辑列表并依次删除最大的数字：

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)

Answer 2

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)

查找列表的子列表并将子列表的总和存储在变量中

Answer 3

首先想到暴力破解。这里很简单，我们可以使用两个 for 循环（嵌套）找到答案。外循环将标记为起点，内循环将转到下一个 M 个元素。
现在是困难的部分，即优化。由于它是一个固定大小的连续子数组，您可以使用两个指针（比如左和右）使 window 固定大小（此处为 M）并保持 window 的大小并继续向右和向右移动继续计算总和并根据需要更新答案。

    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

当然，我们必须检查一些极端情况，例如 M 是否大于数组大小或 M=0

Answer 4

我试过这个解决方案:

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}")

输出：

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

它可能不是最有效的算法，但它确实有效。我得到长度为 M 的所有可能序列并存储最大的总和。

注意：它也适用于@zeeshan12396 案例。

找到大小为 M 的最大连续子数组和

To find max continuous subarray sum of size M

python

python-2.7

python-3.x

python-3.8