线性动态规划：带限制的最大子数组和（限制子数组长度不超过L）

我们先理解一下题意。
题目是经典的最大子数组和的一个变种，但增加了一个约束：子数组的长度不能超过 L。
也就是说，我们不能任意取连续的一段，而必须取长度不超过某个上限 L 的连续子数组，使得它们的和最大。

举个例子：
数组 nums = [3, -1, 5, -2, 6, 2, -3, 4]
L = 3
我们要找一个长度 ≤3 的连续子数组，使得和最大。
这里可以找到子数组 [5, -2, 6] 长度 3，和 9，还有子数组 [6, 2] 长度 2 和 8。
最大的长度不超过 3 的子数组和是 9。

第一步：回顾经典最大子数组和

普通的最大子数组和可以用 Kadane 算法（动态规划思想）求解：
定义 dp[i] 表示以 nums[i] 结尾的最大子数组和，则状态转移为：
dp[i] = max(nums[i], dp[i-1] + nums[i])
最终答案是 max(dp[i] for all i)。
时间复杂度 O(n)。

第二步：增加长度限制 L

现在要求子数组长度 ≤ L，所以 dp[i] 不能简单地用 dp[i-1] 递推，因为 dp[i-1] 对应的子数组长度可能已经是 L，再连上 nums[i] 就长度变成 L+1，违反了约束。
因此 dp 状态需要多一维，记录长度信息？ 或者我们换一种思路：

第三步：重新定义状态

设 dp[i] 表示以 nums[i] 结尾的、长度不超过 L 的子数组的最大和。
为了计算 dp[i]，我们要考虑以 i 结尾的子数组，起点可以是 j，其中 j 从 i-L+1 到 i（当然 j ≥ 0）。
这些子数组的长度是 i-j+1 ≤ L。
那么以 i 结尾、长度不超过 L 的最大子数组和，就是从这些可能的起点 j 中，选一个使得 sum(nums[j..i]) 最大。

但是这样直接枚举 j 是 O(nL) 复杂度，如果 L 和 n 都很大（比如 n=10^5, L=10^4），nL 会到 10^9 不可行。
需要优化。

第四步：优化递推

我们要计算以 i 结尾的长度不超过 L 的最大和，即：

\[dp[i] = \max_{j=\max(0,i-L+1)}^{i} \sum_{k=j}^{i} nums[k] \]

这个区间和可以用前缀和快速计算：

\[sum[j..i] = prefix[i+1] - prefix[j] \]

因此：

\[dp[i] = \max_{j} (prefix[i+1] - prefix[j]) = prefix[i+1] - \min_{j} prefix[j] \]

其中 j ∈ [max(0, i-L+1), i]。

所以问题转化成：
对于每个 i，我们要在 j 的取值范围 [max(0, i-L+1), i] 内，找到最小的 prefix[j]。
然后 dp[i] = prefix[i+1] - min_prefix[j]。
但注意这里的子数组长度是 i-j+1 ≤ L，所以 j 的下界是 i-L+1，上界是 i。
这样计算出的 dp[i] 就是以 i 结尾且长度不超过 L 的子数组的最大和。

最终答案 = max(dp[i]) 对 i=0 到 n-1。

第五步：用滑动窗口最小值加速

我们需要对每个 i，在窗口 [i-L+1, i] 内（j 范围）找最小的 prefix[j]。
注意 j 是到 i 为止，i 是子数组末尾，j 是子数组起点。
那么 prefix[j] 的 j 是在 0 到 n 之间（prefix 长度为 n+1）。
更准确说，我们要在区间 [left, i] 中找最小的 prefix[j]，其中 left = max(0, i-L+1) ？ 不，这里要注意：

当我们固定 i 时，子数组 nums[j..i] 的和是 prefix[i+1] - prefix[j]。
j 的取值范围是 [max(0, i-L+1), i]。
即 j 是起点，范围长度 ≤ L。
我们想要最小化 prefix[j]，因为这样 dp[i] 最大。
所以对每个 i，我们需要在 j ∈ [max(0, i-L+1), i] 内找 prefix[j] 的最小值。

我们可以用单调队列（deque） 在 O(n) 时间里为每个 i 维护这个区间的最小 prefix 值。

第六步：算法步骤

1. 计算前缀和数组 pre，pre[0]=0, pre[i+1]=pre[i]+nums[i]。

2. 初始化一个双端队列 deque 存下标（这些下标对应的 pre 值是单调递增的，队头最小）。

3. 初始化 ans = -inf。

4. 遍历 i 从 0 到 n-1（注意我们要在区间 [left, i] 中找 min(pre[j])，其中 left = max(0, i-L+1)？ 这里小心）
   其实我们遍历的是子数组末尾 i，那么 j 从 i-L+1 到 i，即左边界是 i-L+1，但当 i-L+1<0 时，左边界是 0。
   但单调队列维护的是候选的 j 对应的 pre[j]，j ≤ i，并且 j ≥ i-L+1 才有效。
   所以我们在加入 pre[i] 之前，要先去掉队列中下标 < i-L+1 的过期元素（因为它们作为 j 已经让子数组长度 > L 了）。

   注意顺序：

   • 在计算 dp[i] 时，我们需要的 min(pre[j]) 是在 j 的范围 [i-L+1, i] 内，但 pre 数组长度是 n+1，j 从 0 到 n 都可以，不过这里的 j 指的是子数组起点，对应 pre[j] 的 j 和子数组的 j 一致，但子数组 nums[j..i] 的 sum 是 pre[i+1] - pre[j]。 所以我们需要 pre[j] 的 j 范围是 [max(0, i-L+1), i]。
   • 我们维护的队列里存的是下标 j（对应 pre[j]），并且下标 j 的范围应该是 ≤ i（因为子数组起点不可能在 i 后面）。
   • 每次循环 i 时，先去掉队列中下标 < i-L+1 的元素（因为对于下一个 i+1，起点小于 i+1-L+1 的 j 就过期了，但这里比较绕，我们一步步来）。

   更清晰的做法是：
   我们把 i 看作子数组末尾索引。则子数组和为 pre[i+1] - pre[j]，其中 j ∈ [max(0, i-L+1), i]。
   我们要 min(pre[j])。
   所以我们可以遍历 i 从 0 到 n-1，在 i 循环中：

   1. 当队列非空且队头下标 < i-L+1 时，弹出队头（因为它作为起点 j 已经让子数组长度超过 L 了）。
   2. 用当前队头下标 j0 计算候选和： cand = pre[i+1] - pre[队头]，更新答案 ans = max(ans, cand)。
   3. 在将当前下标 i 加入队列（作为以后的可能 j）之前，先将队尾大于等于 pre[i] 的下标弹出，以保持队列单调递增（因为我们要最小 pre[j]）。
   4. 将 i 加入队尾。

   但这里注意： 当我们计算 cand 时，队列中队头对应的 pre 是最小的，但它对应的 j 可能在 [i-L+1, i] 内吗？
   我们在第1步已经弹出下标 < i-L+1 的，所以队头一定满足 j ≥ i-L+1，并且 j ≤ i 吗？ 不一定，因为我们还没有加入当前的 i，队里存的是 ≤ i-1 的 j。 但我们计算的子数组末尾是 i，起点可以是 i 自身（长度为 1），也可以从前面开始。 所以队头对应的 j 一定 ≤ i-1，但我们要的 j 可以等于 i 吗？ 可以，j=i 时，子数组 nums[i..i] 的和是 nums[i] = pre[i+1] - pre[i]。 所以在计算时，我们要将 i 也作为 j 的候选，那就要在计算前把 i 的 pre[i] 加入队列吗？ 不，应该先加入再算？ 我们仔细设计：

更稳妥的办法：
我们让队列中存的是可能的起点 j 对应的 pre[j]，且队列单调递增。
循环 i 从 0 到 n：

• 当我们考虑子数组末尾是 i-1 时（即 i 从 1 到 n 循环，i 是 pre 的下标，子数组末尾是 i-1），起点 j 范围是 [max(0, (i-1)-L+1), i-1]，也就是 [max(0, i-L), i-1]。
• 在循环 i 时，先把队列中下标 < i-L 的弹出（因为这些起点对于末尾 i-1 来说太早了，会超长，但这里注意 i-L 其实是 left - 1？ 我们重新整理）

为了避免混乱，我们可以用以下框架：

pre[0]=0
for idx=1 to n: pre[idx]=pre[idx-1]+nums[idx-1]

deque = []
ans = -inf
for i in range(0, n):
    # 当前子数组末尾是 i
    # 需要的起点 j 范围是 [max(0,i-L+1), i]
    # 对应的 pre[j] 的下标 j 范围同上
    # 在计算前，移除队列中 j < i-L+1 的
    left = max(0, i-L+1)
    while deque and deque[0] < left:
        deque.popleft()
    # 现在队列中存的是候选起点 j
    if deque:
        cand = pre[i+1] - pre[deque[0]]
        ans = max(ans, cand)
    # 将当前下标 i 作为以后的候选起点加入队列
    # 但加入之前要保持单调递增
    while deque and pre[deque[-1]] >= pre[i]:
        deque.pop()
    deque.append(i)

但这样有个问题：第一次循环 i=0 时，队列为空，cand 不计算，但我们有 nums[0] 单独作为子数组。
所以要初始化 ans = 第一个元素，或者在加入前先算？ 其实可以在队列加入当前 i 之前计算，但这时队列中还没有 i 对应的 pre[i]，所以 j 不能是 i。 但 j 可以是 i 自身（长度为1），对应和是 nums[i]。 所以我们除了看队列，还要考虑单独 nums[i] 作为候选。

所以我们改成：

ans = -inf
deque = deque([0])  # 先把 pre[0]=0 的下标 0 加入
for i in range(0, n):
    left = max(0, i-L+1)
    while deque and deque[0] < left:
        deque.popleft()
    # 以 i 结尾的子数组最大和是 pre[i+1] - pre[deque[0]]
    cand = pre[i+1] - pre[deque[0]]
    ans = max(ans, cand)
    # 将 i+1 作为以后的起点候选加入队列
    while deque and pre[deque[-1]] >= pre[i+1]:
        deque.pop()
    deque.append(i+1)

这里为什么是 i+1 呢？ 因为 pre 数组下标从 0 到 n，子数组 nums[j..i] 的和是 pre[i+1] - pre[j]，j 是起点，j 对应 pre[j] 的下标。 所以我们加入的候选起点是 i+1，但它不是当前的起点，而是以后的起点。 这有点绕。其实更简单的方法：

第七步：简洁算法描述

我们要求 max over all i, j with 0 ≤ j ≤ i and i-j+1 ≤ L of (pre[i+1] - pre[j])。
等价于固定 i，在 j ∈ [i-L+1, i] ∩ [0, i] 中找 min pre[j]。
我们用单调队列维护一个滑动窗口内 pre[j] 的最小值，这个窗口是 j 的范围。
具体步骤：

1. 计算前缀和 pre[0..n]，pre[0]=0。
2. ans = -inf
3. deque 存 j 下标，保持 pre[j] 单调递增
4. 先加入 j=0 到 deque
5. 遍历 i 从 0 到 n-1：
   • 移除 deque 中 j < i-L+1 的（过期起点）
   • 此时队头就是最小 pre[j]，计算 cand = pre[i+1] - pre[deque[0]]，更新 ans
   • 在加入 j=i+1 之前，从队尾弹出 pre[deque[-1]] ≥ pre[i+1] 的
   • 加入 j=i+1 到 deque
6. 返回 ans

注意初始 j=0 是因为子数组可以从 nums[0] 开始，对应的 pre[0]=0。

第八步：实例走一遍

nums = [3, -1, 5, -2, 6, 2, -3, 4]，L=3
pre = [0, 3, 2, 7, 5, 11, 13, 10, 14]
n=8

初始化 deque=[0], ans=-inf

i=0:
移除过期 j<1-3+1=-2? 无
cand = pre[1] - pre[0] = 3-0=3, ans=3
加入 j=1 前，pre[0]=0, pre[1]=3 ≥0? 不弹出，deque=[0,1]

i=1:
移除 j<1-3+1=-1? 无
cand=pre[2]-pre[0]=2-0=2, ans=3
加入 j=2, pre[2]=2, 队尾 pre[1]=3 ≥2，弹出1，deque=[0]，再比 pre[0]=0<2，加入2，deque=[0,2]

i=2:
移除 j<2-3+1=0? 无
cand=pre[3]-pre[0]=7-0=7, ans=7
加入 j=3, pre[3]=7, 队尾 pre[2]=2<7，不弹，deque=[0,2,3]

i=3:
移除 j<3-3+1=1? 移除 j=0, deque=[2,3]
cand=pre[4]-pre[2]=5-2=3, ans=7
加入 j=4, pre[4]=5, 队尾 pre[3]=7≥5 弹出3, deque=[2]，队尾 pre[2]=2<5，加入4, deque=[2,4]

i=4:
移除 j<4-3+1=2? 不移
cand=pre[5]-pre[2]=11-2=9, ans=9
加入 j=5, pre[5]=13, 队尾 pre[4]=5<13，加入5, deque=[2,4,5]

i=5:
移除 j<5-3+1=3? 移除2, deque=[4,5]
cand=pre[6]-pre[4]=13-5=8, ans=9
加入 j=6, pre[6]=10, 队尾 pre[5]=13≥10 弹出5, deque=[4]，队尾 pre[4]=5<10，加入6, deque=[4,6]

i=6:
移除 j<6-3+1=4? 不移
cand=pre[7]-pre[4]=10-5=5, ans=9
加入 j=7, pre[7]=14, 队尾 pre[6]=10<14，加入7, deque=[4,6,7]

i=7:
移除 j<7-3+1=5? 移除4, deque=[6,7]
cand=pre[8]-pre[6]=14-10=4, ans=9
加入 j=8, pre[8]=? 其实 pre 只有下标 0..8，pre[8] 是我们预先算好的 nums 总和 14。
加入前弹出队尾 pre[7]=14 ≥ pre[8]=14? 等于，弹出7, deque=[6]，队尾 pre[6]=10<14，加入8, deque=[6,8]

结束，ans=9，就是子数组 [5, -2, 6] 的和 9。

第九步：复杂度与总结

• 时间复杂度 O(n)，每个元素入队出队一次。
• 空间复杂度 O(L) 用于队列。

这就是求解“长度不超过 L 的最大子数组和”问题的线性动态规划解法，核心是利用前缀和 + 单调队列优化最小值查询。