奥赛求助：长度小于k的最大和子数组问题的O(n)解法

问题定义 #

给定长度为n的整数数组（元素可正可负），寻找连续子数组满足长度严格小于k（即长度可取1到k-1），使得子数组的元素和最大，要求实现O(n)时间复杂度的解法。

第一步：前缀和模型转化 #

连续子数组和问题可以直接通过前缀和映射简化：

• 定义前缀和数组s，其中s[0] = 0，s[i]表示数组前i个元素的累加和，即s[i] = s[i-1] + a[i]。
• 对任意以位置i为结尾的子数组，设其起点为j+1，则：
  • 子数组和 = s[i] - s[j]
  • 子数组长度 = i - j
    结合题目长度约束，可得j的合法范围：
    i - j < k → j > i -k，同时j需满足物理边界0 ≤ j ≤ i-1，因此最终合法区间为 max(0, i -k +1) ≤ j ≤ i-1。
    要让子数组和最大，对固定的s[i]，只需要在合法j区间内找到最小的s[j]，此时的差值就是以i为结尾的所有合法子数组能取得的最大和。

第二步：滑动窗口最小值的O(n)维护 #

上述合法j区间是随i右移不断滑动的固定长度窗口，不需要每次遍历窗口寻找最小值，通过单调递增双端队列即可实现O(1)均摊的窗口最小值查询，整体时间复杂度O(n)：

• 队列存储元素为j的下标，队列内对应s[j]的值保持严格递增
• 遍历到每个位置i时，按以下流程处理：
  1. 将新的候选j = i-1 从队尾入队：从队尾弹出所有对应s[j] ≥ s[i-1]的元素——这类元素的s值更大，且位置比新入队的j更靠左，会更早移出窗口，后续永远不可能成为窗口最小值，直接删除即可
  2. 维护窗口边界：检查队首元素，如果队首的j值小于当前窗口左边界（即j < i -k +1），则从队首弹出，直到队首j落在合法窗口范围内
  3. 此时队首对应的s[j]就是当前窗口的最小值，计算候选子数组和 s[i] - s[queue_front]，和全局最大答案对比更新

参考实现的伪代码逻辑：

dq = deque()
dq.append(0)  # 提前将s[0]入队，匹配j=0的场景
max_sum = -float('inf')
for i in range(1, n+1):
    # 维护队列单调递增
    while dq and s[i-1] <= s[dq[-1]]:
        dq.pop()
    dq.append(i-1)
    # 清理超出窗口左边界的元素
    while dq[0] < i - k + 1:
        dq.popleft()
    # 更新全局最大和
    current = s[i] - s[dq[0]]
    if current > max_sum:
        max_sum = current

复杂度说明 #

每个下标对应的s[j]只会入队1次、出队1次，总操作数和数组长度呈线性关系，加上前缀和数组的计算过程，整体完全满足O(n)的时间复杂度要求。

易错边界提醒 #

• 不要混淆长度约束：题目要求长度小于k，因此窗口左边界是i -k +1，而非求长度不超过k的最大子数组和的左边界
• 全局答案的初始值不能设为0，需要初始化为数组的最小元素——如果数组全为负数，最大子数组和就是数组中最大的单个负数，不能取空数组的0和
• 题目默认k≥2，当k=1时不存在合法的非空子数组，无实际解题意义

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