P4765 有趣的求和（入门）

解题思路

这一题给出一排数字，其中可能有负数，要求找出"连续 L 个数字"之和的最大值。因为数字可正可负，最大和不一定出现在开头，我们只能老老实实地把每一种连续取 L 个的情况都算一遍，再比较出最大。分几步走：

1. 第一步，把区间和变成"一次减法"。 用前缀和数组 prefix，prefix[i] 表示前 i 个数字的和。读入的时候可以边读边建：prefix[i] = prefix[i-1] + 当前数字，一遍输入就把原材料准备好了。从 i 开始的长度为 L 的窗口 [i, i+L-1] 的和，就等于 prefix[i+L-1] - prefix[i-1]。这样每个窗口的和都不需要重新累加，算得飞快。

2. 第二步，枚举每一个窗口。 起点 i 从 1 到 n-L+1，把每个窗口的和都算出来，和当前的最大值 maxSum 比较，大的就更新。可不要因为看到前面已经有一个很大的窗口和就提前停下，后面的窗口可能更大；也不能在遇到负数时就把窗口丢掉，因为后面的正数可能把总和补回来，所以必须一个窗口都不漏地全部检查。

3. 第三步，小心"最大值是负数"这个小坑。 因为数字里有负数，所有窗口的和都可能小于 0。所以 maxSum 的初值不能设成 0，否则答案永远是 0 就错了。正确做法：先把第一个窗口（第 1 到第 L 个数）的和当作 maxSum，再从第二个窗口开始循环比较。这样即使所有窗口和都是负数，也能得到正确结果。

4. 第四步，用样例验证。 n=5，L=4，数字是 -20 30 80 50 40。第一个窗口 -20+30+80+50=140，第二个窗口 30+80+50+40=200，取较大的 200，和样例输出一致。

5. 第五步，记住两个数据上的提醒。 本题 n 实际上可以高达 1000000，前缀和数组必须开到至少 1000005；而且最好把数组放到函数外面（全局数组），避免占用过多栈内存。前缀和的值很大，要用 long long 存储。

6. 第六步，看看两个小边界。 如果 L=1，每个窗口就只有一个数字，答案就是这排数字里的最大值，算法一样算得对；如果 L=n，整排只有一个窗口，答案就是所有数字之和，循环一次都不跑也没问题。

参考代码

// 求长度为L的连续数字之和的最大值（数字可能是负数）：前缀和枚举每个窗口
#include <iostream>
long long prefix[1000005]; // 全局前缀和数组，n 最大可达 1000000，放全局避免栈溢出
int main() {
    int n, L;
    std::cin >> n >> L;
    for (int i = 1; i <= n; ++i) {
        long long num;
        std::cin >> num;
        prefix[i] = prefix[i - 1] + num;
    }
    long long maxSum = prefix[L] - prefix[0]; // 先取第一个长度为L的窗口
    for (int i = 2; i + L - 1 <= n; ++i) {
        long long curSum = prefix[i + L - 1] - prefix[i - 1]; // 窗口 i ~ i+L-1 的和
        if (curSum > maxSum) maxSum = curSum;
    }
    std::cout << maxSum << '\n';
    return 0;
}

复杂度分析

建前缀和需要 O(n)，枚举所有长度为 L 的窗口也是 O(n)，所以时间复杂度 O(n)，空间复杂度 O(n)。n 最大 1000000，大约 200 万次操作，1 秒内能轻松完成。数组是全局的、不占栈空间，即使 n 很大也不会栈溢出，这是大数组题目的小技巧。