P4764 最大区间和（入门）

解题思路

这道题和"K个元素和"是兄弟题，目标却不一样：上一题要把所有长度为 K 的区间和都输出出来，这一题只要找出其中最大的那个，并且把它的起点和终点下标输出（下标从 1 开始）。这里的"区间"就是指连续的一段数，比如第 3 到第 5 个数，就是一个长度为 3 的区间。可以分几步来做：

1. 第一步，认识"区间和"怎么快速算。 如果每次都把区间里的数从头加一遍，最坏要 O(n*K) 次，K 接近 n 时会退化到 2500 亿次，一定会超时。所以我们要用前缀和：开一个数组 prefix，让 prefix[i] 存"前 i 个数的总和"。怎么造 prefix 呢？读数字的时候一边读一边加：prefix[i] = prefix[i-1] + 第 i 个数，一遍读入就顺便建好了。有了它，从 i 开始、长度为 K 的区间 [i, i+K-1] 的和，只要算一次减法：prefix[i+K-1] - prefix[i-1]。这就像提前把每段路的路程都写在路牌上，问哪段路长，看一眼两个路牌的差就行。

2. 第二步，从头到尾枚举每一个起点。 起点 i 可以从 1 一直走到 n-K+1，每个起点对应一个长度为 K 的区间。每算出一个区间和 curSum，就和当前记录的答案 maxSum 比一比：如果更大，就更新 maxSum，同时记下这个区间的起点 bestLeft 和终点 bestRight。注意代码里循环从 i=2 开始，因为 i=1 那个窗口在初始化时已经算过了，不用重复算。

3. 第三步，盯紧"第一个最大"这个细节。 题目要求：如果有好几个区间和一样大，输出第一个出现的位置。所以更新的时候要写成 if (curSum > maxSum)，只有严格更大才更新；如果用 >=，遇到一样大的就会把后面的位置盖掉，就找不到"第一个"了。

4. 第四步，用样例亲手验一遍。 n=10，K=3，数组是 2 1 3 6 4 5 8 7 5 3。依次枚举：i=1 得 6，i=2 得 10，i=3 得 13，i=4 得 15，i=5 得 17，i=6 得 20（此时更新），i=7 也得 20 但和答案相等、不更新，i=8 得 15。最大和是 20，位置是第 6 到第 8 个数，输出 20 和 6 8，和样例完全一致。

5. 第五步，别忘了防溢出的两个习惯。 数组要开到 500005 左右；前缀和可能超过 int 的范围，所以 prefix 要用 long long 存，防止中途溢出算错。

6. 第六步，留意小数据边界。 如果 n 恰好等于 K，整段数组只有一个窗口，循环一次都不跑，直接输出初始化的答案，也能得到正确答案，不用单独特判。

参考代码

// 求所有连续且长度为K的区间中最大的区间和，并输出该区间的起点和终点（第一个最大者）
#include <iostream>
int main() {
    int n, K;
    std::cin >> n >> K;
    long long prefix[500005] = {0}; // prefix[i] 表示前 i 个数的和
    for (int i = 1; i <= n; ++i) {
        long long num;
        std::cin >> num;
        prefix[i] = prefix[i - 1] + num;
    }
    long long maxSum = prefix[K] - prefix[0]; // 先设第一个长度为K的区间为最大
    int bestLeft = 1, bestRight = K;
    for (int i = 2; i + K - 1 <= n; ++i) {
        long long curSum = prefix[i + K - 1] - prefix[i - 1]; // 区间 [i, i+K-1] 的和
        if (curSum > maxSum) { // 严格大于才更新，保证保留第一个最大值
            maxSum = curSum;
            bestLeft = i;
            bestRight = i + K - 1;
        }
    }
    std::cout << maxSum << '\n';
    std::cout << bestLeft << ' ' << bestRight << '\n';
    return 0;
}

复杂度分析

建立前缀和是 O(n)，枚举所有长度为 K 的区间也是 O(n)，所以总时间复杂度 O(n)，空间复杂度 O(n)。n 最大 500000，大约 100 万次操作，非常快。如果不用前缀和而是每个区间从头加，最坏要 O(n*K) 次，K 接近 n 时会退化到 2500 亿次，一定会超时。