带限制的最大子数组和（限制子数组必须包含至少k个元素）

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

解题过程：

1. 问题分析：

• 这是最大子数组和问题的变种，增加了子数组长度至少为k的限制
• 普通的最大子数组和问题可以用Kadane算法在O(n)时间内解决
• 但加入长度限制后，问题变得更加复杂

2. 基本思路：

• 我们可以使用前缀和数组来优化计算
• 定义前缀和数组prefix，其中prefix[i]表示nums[0]到nums[i-1]的和
• 那么子数组nums[i..j]的和可以表示为prefix[j+1] - prefix[i]

3. 动态规划解法：

• 我们需要找到满足j-i+1 ≥ k的最大(prefix[j+1] - prefix[i])
• 对于每个j（j ≥ k-1），我们需要找到i ≤ j-k+1，使得prefix[i]最小
• 这样prefix[j+1] - prefix[i]就是最大的

4. 具体步骤：
   步骤1：计算前缀和数组

prefix[0] = 0
for i in range(1, n+1):
    prefix[i] = prefix[i-1] + nums[i-1]

步骤2：维护最小前缀和

• 我们维护一个变量min_prefix，表示当前遇到的最小前缀和
• 但需要注意：由于子数组长度至少为k，所以当我们计算到位置j时，只能使用位置≤j-k的前缀和

步骤3：遍历求解

max_sum = -float('inf')
min_prefix = prefix[0]  # 初始最小前缀和是prefix[0]

for j in range(k-1, n):
    # 更新最小前缀和：考虑位置j-k+1之前的前缀和
    if j >= k:
        min_prefix = min(min_prefix, prefix[j-k+1])
    
    # 计算当前子数组和：prefix[j+1] - min_prefix
    current_sum = prefix[j+1] - min_prefix
    max_sum = max(max_sum, current_sum)

5. 算法正确性证明：

• 对于每个结束位置j，我们考虑所有起始位置i ≤ j-k+1的子数组
• 我们始终维护了i ≤ j-k+1的最小prefix[i]
• 因此prefix[j+1] - min_prefix就是结束于j的最优解
• 遍历所有j就得到了全局最优解

6. 时间复杂度分析：

• 计算前缀和：O(n)
• 遍历数组：O(n)
• 总体时间复杂度：O(n)
• 空间复杂度：O(n)（用于存储前缀和数组）

7. 示例演示：
   输入：nums = [2, 1, -3, 4, -1, 2, 1, -5, 4], k = 3

计算前缀和：
prefix = [0, 2, 3, 0, 4, 3, 5, 6, 1, 5]

遍历过程：

• j=2: min_prefix=min(prefix[0])=0, current_sum=prefix[3]-0=0, max_sum=0
• j=3: min_prefix=min(0, prefix[1])=min(0,2)=0, current_sum=4-0=4, max_sum=4
• j=4: min_prefix=min(0, prefix[2])=min(0,3)=0, current_sum=3-0=3, max_sum=4
• j=5: min_prefix=min(0, prefix[3])=min(0,0)=0, current_sum=5-0=5, max_sum=5
• j=6: min_prefix=min(0, prefix[4])=min(0,4)=0, current_sum=6-0=6, max_sum=6
• j=7: min_prefix=min(0, prefix[5])=min(0,3)=0, current_sum=1-0=1, max_sum=6
• j=8: min_prefix=min(0, prefix[6])=min(0,5)=0, current_sum=5-0=5, max_sum=6

结果为6，对应子数组[4, -1, 2, 1]

8. 边界情况处理：

• 当k > n时，无解（但题目通常保证k ≤ n）
• 当所有数都是负数时，需要选择绝对值最小的负数子数组
• 当k=1时，退化为普通的最大子数组和问题

这个算法巧妙地结合了前缀和和滑动窗口的思想，在O(n)时间内解决了带长度限制的最大子数组和问题。