带限制条件的最大子数组和（限制子数组长度至少为L）

让我为你详细讲解这个线性动态规划问题。

问题描述

给定一个整数数组nums和一个整数L，要求找到一个长度至少为L的连续子数组，使得该子数组的和最大。返回这个最大的和。

示例：

输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4], L = 3
输出：6
解释：子数组 [4, -1, 2, 1] 的和最大，为6，且长度为4 ≥ 3

解题思路

基础思路分析

这个问题是最大子数组和问题的变种，增加了子数组长度至少为L的限制。我们不能简单地使用标准的Kadane算法，因为需要保证子数组长度满足条件。

动态规划解法

步骤1：定义状态

我们使用两个数组来记录状态：

• dp[i]：表示以第i个元素结尾的长度至少为L的最大子数组和
• prefixSum[i]：表示前i个元素的前缀和，即nums[0] + nums[1] + ... + nums[i-1]

步骤2：状态转移方程

对于每个位置i（从L开始）：

1. 计算以i结尾的长度恰好为L的子数组和：prefixSum[i+1] - prefixSum[i+1-L]
2. 考虑将当前元素加入到前一个最大子数组中：dp[i-1] + nums[i]
3. 取两者的最大值：dp[i] = max(prefixSum[i+1] - prefixSum[i+1-L], dp[i-1] + nums[i])

步骤3：初始化

• prefixSum[0] = 0
• 对于i < L，dp[i]可以初始化为一个很小的值，因为长度不够L

步骤4：最终结果

遍历所有dp[i]，取最大值

详细解题过程

让我通过一个具体例子来演示：

nums = [1, -2, 3, 4, -5, 6], L = 3

步骤1：计算前缀和

index:   0   1   2   3   4   5
nums:    1  -2   3   4  -5   6
prefix:  0   1  -1   2   6   1   7

步骤2：动态规划计算

i = 2 (第一个满足长度≥3的位置)

• 长度恰好为3的和：prefix[3] - prefix[0] = 2 - 0 = 2
• dp[2] = 2

i = 3

• 长度恰好为3的和：prefix[4] - prefix[1] = 6 - 1 = 5
• 扩展前一个：dp[2] + nums[3] = 2 + 4 = 6
• dp[3] = max(5, 6) = 6

i = 4

• 长度恰好为3的和：prefix[5] - prefix[2] = 1 - (-1) = 2
• 扩展前一个：dp[3] + nums[4] = 6 + (-5) = 1
• dp[4] = max(2, 1) = 2

i = 5

• 长度恰好为3的和：prefix[6] - prefix[3] = 7 - 2 = 5
• 扩展前一个：dp[4] + nums[5] = 2 + 6 = 8
• dp[5] = max(5, 8) = 8

步骤3：找到最大值

max(dp[2], dp[3], dp[4], dp[5]) = max(2, 6, 2, 8) = 8

对应子数组：[3, 4, -5, 6]，和为8，长度4 ≥ 3

算法优化

上面的解法时间复杂度是O(n)，空间复杂度也是O(n)。我们可以进一步优化空间复杂度到O(1)：

def maxSubarrayWithMinLength(nums, L):
    n = len(nums)
    if n < L:
        return sum(nums)
    
    # 计算第一个长度为L的子数组和
    current_sum = sum(nums[:L])
    max_sum = current_sum
    
    # 维护以当前元素结尾的长度至少为L的最大子数组和
    dp = current_sum
    
    for i in range(L, n):
        # 当前长度为L的子数组和
        current_sum = current_sum + nums[i] - nums[i - L]
        
        # 更新dp：要么是当前长度为L的子数组，要么是扩展前一个
        dp = max(current_sum, dp + nums[i])
        
        # 更新全局最大值
        max_sum = max(max_sum, dp)
    
    return max_sum

复杂度分析

• 时间复杂度：O(n)，只需要遍历数组一次
• 空间复杂度：O(1)，只使用了常数个额外变量

关键点总结

1. 前缀和技巧：快速计算任意子数组的和
2. 状态定义：dp[i]表示以i结尾的长度至少为L的最大子数组和
3. 状态转移：比较"恰好长度为L"和"扩展前一个"两种情况
4. 边界处理：注意数组长度小于L的情况

这个解法巧妙地结合了前缀和和动态规划，在保证长度限制的同时找到了最大子数组和。