滑动窗口求数组1~n长连续子数组最大和：含负数时代码失效

问题根源 #

1. 全局max未重置
   你的代码中max变量仅在程序开头初始化一次，计算不同长度k的子数组时，会保留之前长度的最大值。比如示例中，k=2时max为10，k=3时所有子数组和（5、3）都小于10，因此输出仍为10，而非预期的5。

2. 数组越界访问
   内层循环中，当i + j >= n时会访问数组外的内存。例如n=4、k=3时，i=2的情况下，j=2会导致j+i=4，超出数组索引范围（0-3），引发未定义行为。

3. max初始值不合理
   固定将max设为-50，若数组所有元素均为小于-50的负数，计算结果会完全错误。

修正后的代码 #

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    for (int k = 1; k <= n; k++) {
        // 初始化当前长度k的子数组最大和为第一个子数组的和
        int current_max = 0;
        for (int j = 0; j < k; j++) {
            current_max += arr[j];
        }
        
        // 滑动窗口计算后续子数组的和
        for (int i = 1; i <= n - k; i++) {
            int current_sum = current_max - arr[i-1] + arr[i + k - 1];
            if (current_sum > current_max) {
                current_max = current_sum;
            }
        }
        
        printf("%d\n", current_max);
    }
    return 0;
}

修改说明 #

• 按子数组长度重置最大值：每个k对应的current_max都重新初始化，仅针对当前长度的子数组计算最大值，不受之前结果干扰。
• 滑动窗口优化：摒弃三层嵌套循环，通过滑动窗口复用前一个子数组的和（减去左端元素、加上右端新元素），将时间复杂度从O(n³)降至O(n²)，同时通过循环条件i <= n - k避免数组越界。
• 动态初始化最大值：用当前长度k的第一个子数组和作为初始current_max，适配所有元素场景（包括全负数数组）。

测试结果 #

输入示例：

4
3
7
-5
1

输出：

7
10
5
6

与预期完全一致。

内容的提问来源于stack exchange，提问作者ArianMohseni