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

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

例如，对于nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]，L = 3：

• 长度为3的子数组[4, -1, 2]的和为5
• 长度为4的子数组[4, -1, 2, 1]的和为6
• 但最优解是长度为6的子数组[4, -1, 2, 1, -5, 4]的和为5？不对，这个和是4+(-1)+2+1+(-5)+4=5
• 实际上最优解是[4, -1, 2, 1]的和为6

解题思路
这个问题可以分解为两个部分：

1. 计算前缀和数组，方便快速计算任意子数组的和
2. 对于每个可能的子数组结束位置，找到最优的开始位置

详细解题步骤

步骤1：理解问题核心
普通的最大子数组和问题可以用Kadane算法在O(n)时间内解决，但加上"长度至少为L"的限制后，问题变得复杂。我们需要保证找到的子数组长度≥L。

步骤2：前缀和数组
首先计算前缀和数组prefix，其中prefix[i]表示前i个元素的和：

• prefix[0] = 0
• prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

这样，子数组nums[i..j]的和可以表示为prefix[j+1] - prefix[i]。

步骤3：关键思路
对于每个结束位置j（j ≥ L-1），我们需要找到开始位置i（0 ≤ i ≤ j-L+1），使得prefix[j+1] - prefix[i]最大。

这等价于对于每个j，找到i ∈ [0, j-L+1]使得prefix[i]最小。

步骤4：动态规划实现
我们可以维护一个min_prefix数组，其中min_prefix[j]表示prefix[0]到prefix[j]中的最小值。

算法步骤：

1. 计算前缀和数组prefix
2. 初始化最大和为负无穷
3. 遍历所有可能的结束位置j（从L-1到n-1）
4. 对于每个j，计算当前可能的最大和：prefix[j+1] - min_prefix[j-L+1]
5. 更新全局最大和

步骤5：具体例子演示
以nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]，L = 3为例：

1. 计算前缀和：
   index: 0 1 2 3 4 5 6 7 8 9
   nums: -2 1 -3 4 -1 2 1 -5 4
   prefix: 0 -2 -1 -4 0 -1 1 2 -3 1

2. 遍历过程：

   • j=2：i范围[0,0]，min_prefix[0]=0，和=prefix[3]-prefix[0]=-4-0=-4
   • j=3：i范围[0,1]，min_prefix[1]=min(0,-2)=-2，和=prefix[4]-min_prefix[1]=0-(-2)=2
   • j=4：i范围[0,2]，min_prefix[2]=min(-2,-1,-4)=-4，和=prefix[5]-min_prefix[2]=-1-(-4)=3
   • j=5：i范围[0,3]，min_prefix[3]=-4，和=prefix[6]-min_prefix[3]=1-(-4)=5
   • j=6：i范围[0,4]，min_prefix[4]=-4，和=prefix[7]-min_prefix[4]=2-(-4)=6 ← 最大值
   • j=7：i范围[0,5]，min_prefix[5]=-4，和=prefix[8]-min_prefix[5]=-3-(-4)=1
   • j=8：i范围[0,6]，min_prefix[6]=-4，和=prefix[9]-min_prefix[6]=1-(-4)=5

最大和为6，对应子数组[4, -1, 2, 1]。

步骤6：算法优化
上面的min_prefix数组可以进一步优化，我们不需要存储整个数组，只需要在遍历过程中维护当前的最小前缀和。

优化后的伪代码：

max_sum = -∞
min_prefix = prefix[0]  // 初始为prefix[0]=0

for j from L-1 to n-1:
    // 更新最小前缀和（注意索引范围）
    if j-L >= 0:
        min_prefix = min(min_prefix, prefix[j-L+1])
    
    current_sum = prefix[j+1] - min_prefix
    max_sum = max(max_sum, current_sum)

步骤7：时间复杂度分析

• 前缀和计算：O(n)
• 主循环：O(n)
• 总时间复杂度：O(n)
• 空间复杂度：O(n)（存储前缀和数组）

这个算法高效地解决了带长度限制的最大子数组和问题，通过巧妙利用前缀和和滑动最小值的概念，在O(n)时间内得到最优解。