解题思路

题目在说什么？

有一排 n 个数，我们要在它们里面挑相邻的 4 个数，使这 4 个数的和最大，并告诉这个最大和的起始位置（从 1 开始数）。如果有多处都是最大和，选最左边的那一处。

怎么枚举每一段？

假设数组的下标从 0 开始，第一个数是 a[0]，最后一个数是 a[n-1]。

• 以位置 0 开头的连续 4 个数是：a[0]+a[1]+a[2]+a[3]；
• 以位置 1 开头的连续 4 个数是：a[1]+a[2]+a[3]+a[4]；
• ……
• 以位置 n-4 开头的连续 4 个数是：a[n-4]+a[n-3]+a[n-2]+a[n-1]，这是最后一组。

所以只要让 i 从 0 走到 n-4，枚举每一个开头位置，就能覆盖所有可能的“相邻 4 个数”。

怎么记录答案？

用两个变量：

• best：目前找到的最大和；
• pos：最大和对应的起始位置（输出时用 1 开始编号，所以记 i+1）。

因为题目说所有数都是正整数，best 初始设为 0 是安全的：只要找到一个窗口，和就一定比 0 大。每次算出一个窗口的和 s，如果 s > best 就更新。注意用的是严格大于，这样当最大和出现多次时，我们保留的是最左边的那一次，正好符合题意。

参考代码

// P4501 找出相邻4个数相加之和最大及其起始位置
#include <iostream>
using namespace std;
int main() {
    int n, a[25];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];  // 读入n个数
    int best = 0, pos = 1;                     // best最大和，pos起始位置(从1开始)
    for (int i = 0; i <= n - 4; i++) {
        int s = a[i] + a[i + 1] + a[i + 2] + a[i + 3]; // 以i开头的连续4个数之和
        if (s > best) { best = s; pos = i + 1; }       // 更新最大和和位置
    }
    cout << best << endl << pos << endl;
    return 0;
}

复杂度分析

设有 n 个数。

• 时间：一共要检查 n-3 个窗口，每个窗口只做 4 次加法，所以时间复杂度是 O(4×(n-3))，也就是 O(n)；
• 空间：需要一个能装下 n 个数的数组，空间复杂度是 O(n)。