带长度约束的最大子数组算法实现失败，运行结果与预期不符

前缀和数组B的定义 #

你对B数组的理解是错误的，标准的用于子数组和计算的前缀和数组定义如下：

• B[0] = 0，作为前缀和的基准初始值
• B[i] = A[0] + A[1] + ... + A[i-1]，对应数组A前i个元素的累加和
• B数组的长度是len(A)+1，比A数组多1，不是少1

你给出的示例A = [8, -1, -1, 4, -2, -3, 5, 6, -3]，对应的正确B数组为：
[0, 8, 7, 6, 10, 8, 5, 10, 16, 13]
你之前写的B数组漏了开头的0，也没有对应第一个元素的前缀值，所以是错误的。

代码问题排查 #

你的代码存在两个核心错误：

1. 前缀和构造逻辑完全错误
   你当前构造的b数组既没有初始基准值0，累加逻辑也不符合前缀和的定义，无法覆盖从A数组首元素开始的子数组求和场景，比如你要的结果16对应子数组A[0:8]的和，需要用B[8]-B[0]计算，你的b数组里没有0这个值，永远得不到这个结果。
2. 求和逻辑遗漏了有效子数组的判断边界
   你在遍历过程中没有限制子数组至少包含一个元素，可能会出现无效的空数组求和情况。

修正后的代码 #

from collections import deque
def maxSubseq(a, k):
    maxSum = -float('inf')
    # 构造正确的前缀和数组
    n = len(a)
    b = [0]*(n+1)
    for i in range(n):
        b[i+1] = b[i] + a[i]
    
    deq = deque()
    for q in range(len(b)):
        # 窗口长度超过k时弹出队首
        if deq and q - deq[0] > k:
            deq.popleft()
        # 维护单调递增队列
        while deq and b[deq[-1]] > b[q]:
            deq.pop()
        deq.append(q)
        # 计算当前最大子数组和，至少要有一个元素的子数组才参与计算
        if q >= 1:
            current_sum = b[q] - b[deq[0]]
            if current_sum > maxSum:
                maxSum = current_sum
    return maxSum

调用print(maxSubseq([8, -1, -1, 4, -2, -3, 5, 6, -3], 8))即可得到正确结果16。

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