最多含K个元素的子数组最大和求解：问题排查与优化方案

给定整数数组与正整数k，找出长度≤k的子数组的最大和（子数组为数组的连续部分）。例如数组[5, -3, 5, 5, -3, 5]、k=3时，最大和为10，对应子数组[5, 5]。

我最初尝试结合Kadane算法与大小为K的滑动窗口实现，代码如下：

maxi = nums[0]
max_so_far = 0
prev = 0
for i in range(len(nums)):
    max_so_far += nums[i]
    if (i - prev) >= k:
        max_so_far -= nums[prev]
        prev += 1
    maxi = max(maxi, max_so_far)
    if max_so_far < 0:
        max_so_far = 0
        prev = i + 1
return maxi

但该方案无法通过以下测试用例：

nums = [5, -3, 5, 5, -3, 5]
k = 3

正确解法：前缀和 + 单调队列（时间复杂度O(n)） #

def maxSubarraySum(self, nums, k) -> int:
    prefix_sum = [0] * len(nums)
    prefix_sum[0] = nums[0]
    for i in range(1, len(nums)):
        prefix_sum[i] = prefix_sum[i-1] + nums[i]
    q = deque()
    for i in range(k):
        while len(q) > 0 and prefix_sum[i] >= prefix_sum[q[-1]]:
            q.pop()
        q.append(i)
    maxi = max(prefix_sum[:k])
    for i in range(1, len(nums)):
        if q[0] < i:
            q.popleft()
        if i + k - 1 < len(nums):
            while len(q) > 0 and prefix_sum[i + k - 1] >= prefix_sum[q[-1]]:
                q.pop()
            q.append(i + k - 1)
        maxi = max(maxi, prefix_sum[q[0]] - prefix_sum[i-1])
    return maxi

内容的提问来源于stack exchange，提问作者Tarun