题目重点：Oracle 后端与数据面经的连续子数组题；用前缀和与单调队列在线性时间处理负数和长度上限。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版要求非空连续子数组，输入数组非空且 K>0；若 K>N，则上限等价于 N。
- 元素可为负，求真实最大和而非与 0 比较；空输入或非法 K 报错。
解题路线
- 设前缀和 P[j]=前 j 项和，以 j 结尾的子数组和为 P[j]−P[i]，长度约束给 i∈[j−K,j−1]。所以每个 j 需要这个范围内的最小 P[i]。
- 双端队列存前缀下标与值，前端是当前窗口最小值；先移除 i<j−K 的过期前缀，再用前端计算候选。
- 把当前 P[j] 加入队列时，从尾部弹掉值大于等于 P[j] 的项：新前缀更小且下标更晚，在未来窗口中不会比旧项先过期，因此旧项永不更优。
- 每个前缀只入队与出队各一次，处理所有长度而无需枚举 O(NK) 子数组。
手动走一遍
数组 [4,-10,5,6]、K=2：最优是 [5,6]，和 11。固定长度 K 的窗口只能看到 [4,-10]、[-10,5]、[5,6]，在此例碰巧也能找到；但 [-5,4,-5]、K=2 时最优长度 1 是 [4]，固定长度法会错。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Maximum nonempty subarray sum with length at most k, including negatives."""
from collections import deque
def max_subarray_at_most_k(values: list[int], k: int) -> int:
if not values or k <= 0:
raise ValueError("values must be nonempty and k must be positive")
prefix = 0
minimums: deque[tuple[int, int]] = deque([(0, 0)])
best: int | None = None
for end, value in enumerate(values, start=1):
prefix += value
while minimums and minimums[0][0] < end - k:
minimums.popleft()
candidate = prefix - minimums[0][1]
best = candidate if best is None else max(best, candidate)
while minimums and minimums[-1][1] >= prefix:
minimums.pop()
minimums.append((end, prefix))
assert best is not None
return best
复杂度
N 项时间 O(N)，队列最坏 O(min(N,K)) 空间，前缀和流式累计无需整张前缀数组。若只求数值，可边读边处理；若要返回下标，在最佳候选更新时记录队首和 j。
易错点与追问
容易失分的边界
- 用标准 Kadane 只求任意长度最大和，违反 K 上限。
- 使用固定 K 长度滑动窗，漏掉更短的最优子数组。
- 把空子数组当作和 0，在全负输入上错误返回 0。
- 先把 P[j] 入队再算候选，可能取 i=j 的空子数组。
继续深挖
- 如果长度必须至少 L 且最多 K，如何调整可入队下标与过期边界？
- 若元素持续流入，怎样保存最近 K 个前缀并维护在线最大值？
- 如果要求所有达到最大和的区间，输出规模可能怎样增长？
