线性动态规划：最大子数组和问题的变种——至少包含k个元素的最大子数组和

今天我们来讲解一个最大子数组和问题的变种：给定一个整数数组和一个整数k（k ≥ 1），要求找到一个长度至少为k的连续子数组，使其和最大。

问题描述

输入：

• 一个整数数组 nums（长度 n ≥ 1）
• 一个整数 k（1 ≤ k ≤ n）

输出：

• 一个连续子数组（长度至少为 k）的最大可能和。

示例：

输入：nums = [-2, 2, -3, 4, -1, 2, 1, -5, 4], k = 3
输出：6
解释：子数组 [4, -1, 2, 1] 的和为 6，且长度至少为 3。

为什么不是整个数组的最大子数组和 [2, -3, 4, -1, 2, 1] 的和 5？因为题目要求长度至少为k，如果k=3，那么可以找到更长的子数组 [4, -1, 2, 1] 和更大（6）。注意，经典的最大子数组和（Kadane算法）找到的是任意长度子数组的最大和，而这里限制了最小长度k，所以解法和结果可能不同。

解题思路

这个问题可以分解为两步：

1. 计算固定长度至少为k的子数组的和的最大值。
2. 但直接枚举所有长度≥k的子数组会超时（O(n²)），所以需要更高效的动态规划方法。

第一步：问题分析

设数组为 nums[0..n-1]，目标长度为 k。

我们需要对于每个结束位置j，找到一个起始位置i，使得 j - i + 1 ≥ k，并且 sum(nums[i..j]) 最大。

换句话说：

• 对于每个 j，我们需要找 max_{i ≤ j-k+1} (sum[j] - sum[i-1])，其中 sum 是前缀和数组（sum[m] = nums[0] + ... + nums[m]，定义 sum[-1] = 0 方便计算）。
• 因为 j-i+1 ≥ k 等价于 i ≤ j-k+1。

所以问题转化为：对于每个 j，在区间 [0, j-k+1] 内找最小的 sum[i-1]（因为 sum[j] - sum[i-1] 最大等价于 sum[i-1] 最小）。

这样，我们可以通过维护一个滑动窗口最小值来高效解决。

第二步：动态规划解法（一维DP）

定义：

• dp[j]：表示以 j 为结尾、长度至少为 k 的子数组的最大和。

但直接这样定义转移比较复杂，因为长度至少为k，可能由更长的子数组延伸而来。更好的方法是：

方法：前缀和 + 最小前缀和滑动窗口

1. 计算前缀和数组 prefix，prefix[i] = sum(nums[0..i-1])，其中 prefix[0] = 0，prefix[i] = prefix[i-1] + nums[i-1]（i从1到n）。
   这样，子数组 nums[i..j] 的和 = prefix[j+1] - prefix[i]。

2. 对于每个结束位置 j（0 ≤ j < n），我们需要找起始位置 i 满足 j - i + 1 ≥ k，即 i ≤ j - k + 1。
   那么子数组和 = prefix[j+1] - prefix[i]。
   为了最大化这个值，我们需要在 i ≤ j-k+1 的范围内找到最小的 prefix[i]。

3. 所以我们可以维护一个变量 minPrefix，表示在当前位置 j 之前至少 k-1 个位置的最小前缀和。
   具体来说，对于 j，我们考虑 minPrefix = min(prefix[0], prefix[1], ..., prefix[j-k+1])。
   那么 dp[j] = prefix[j+1] - minPrefix 就是以j结尾、长度至少为k的子数组的最大和。

4. 最终答案就是所有 dp[j] 的最大值。

第三步：逐步演算

以示例 nums = [-2, 2, -3, 4, -1, 2, 1, -5, 4], k=3 为例。

1. 计算前缀和 prefix：

   nums: [-2, 2, -3, 4, -1, 2, 1, -5, 4]
   prefix: [0, -2, 0, -3, 1, 0, 2, 3, -2, 2]
   索引i:  0   1  2   3  4  5  6  7   8  9   (prefix的索引)
   对应原数组： prefix[i] 是 nums[0..i-1] 的和。
   

2. 开始遍历 j 从 0 到 n-1：

   • j=0：需要长度≥3，但 j=0 时长度最多为1，不满足，跳过（或者初始化为极小值）。
   • j=1：长度最多为2，不满足，跳过。
   • j=2：需要 i ≤ j-k+1 = 0。所以 i 只能是 0。
     子数组和 = prefix[3] - prefix[0] = -3 - 0 = -3。
     目前最大和 = -3。
   • j=3：需要 i ≤ 1。考虑 i=0 和 i=1。
     minPrefix = min(prefix[0], prefix[1]) = min(0, -2) = -2。
     子数组和 = prefix[4] - minPrefix = 1 - (-2) = 3。
     更新最大和 = max(-3, 3) = 3。
   • j=4：需要 i ≤ 2。考虑 i=0,1,2。
     minPrefix = min(prefix[0], prefix[1], prefix[2]) = min(0, -2, 0) = -2。
     子数组和 = prefix[5] - (-2) = 0 - (-2) = 2。
     最大和 = max(3, 2) = 3。
   • j=5：需要 i ≤ 3。考虑 i=0,1,2,3。
     minPrefix = min(0, -2, 0, -3) = -3。
     子数组和 = prefix[6] - (-3) = 2 - (-3) = 5。
     最大和 = max(3, 5) = 5。
   • j=6：需要 i ≤ 4。考虑 i=0..4。
     minPrefix = min(0, -2, 0, -3, 1) = -3。
     子数组和 = prefix[7] - (-3) = 3 - (-3) = 6。
     最大和 = max(5, 6) = 6。
   • j=7：需要 i ≤ 5。考虑 i=0..5。
     minPrefix = min(0, -2, 0, -3, 1, 0) = -3。
     子数组和 = prefix[8] - (-3) = -2 - (-3) = 1。
     最大和 = max(6, 1) = 6。
   • j=8：需要 i ≤ 6。考虑 i=0..6。
     minPrefix = min(0, -2, 0, -3, 1, 0, 2) = -3。
     子数组和 = prefix[9] - (-3) = 2 - (-3) = 5。
     最大和 = 6。

最终答案是 6。

第四步：算法实现

我们可以在一次遍历中同时维护 minPrefix 和 maxSum，避免存储所有 dp[j]。

伪代码：

function maxSubarrayAtLeastK(nums, k):
    n = nums.length
    prefix = array of size n+1
    prefix[0] = 0
    for i from 1 to n:
        prefix[i] = prefix[i-1] + nums[i-1]
    
    maxSum = -infinity
    minPrefix = infinity  // 用于滑动窗口维护最小值
    
    for j from k-1 to n-1:  // 因为长度至少k，所以j从k-1开始才有意义
        // 维护 minPrefix，它对应的是 prefix[0..j-k]
        if j-k >= 0:
            minPrefix = min(minPrefix, prefix[j-k])
        else:
            minPrefix = min(minPrefix, 0)  // 当j-k=-1时，考虑prefix[0]
        
        // 计算以j结尾的长度至少为k的子数组最大和
        current = prefix[j+1] - minPrefix
        maxSum = max(maxSum, current)
    
    return maxSum

时间复杂度：O(n)
空间复杂度：O(n)（前缀和数组），可以优化为 O(1) 如果不需要存储所有前缀和，但需要小心维护 minPrefix。

第五步：边界情况

• 如果 k=1，那么就是经典的最大子数组和问题。
• 如果所有元素都是负数且 k>1，那么答案可能是某个长度≥k的负数子数组的和，需要正确计算。
• 如果 n=k，那么整个数组的和就是答案。
• 注意整数溢出问题（如果和可能很大，用 long long 类型）。

总结

这个问题的核心是将长度限制转化为前缀和差的最大化，并利用滑动窗口维护最小前缀和。它拓展了经典的最大子数组和问题，要求子数组长度至少为k，通过前缀和技巧和一次遍历，我们可以在 O(n) 时间内高效求解。