C++ 滑动窗口求解连续子数组最大和问题

好的，这是一个非常经典的 **滑动窗口最大值** 问题。你要求的是“危险程度最高的k个连续的人” —— 实际上题目描述的意思是 **寻找长度为k的连续子数组的最大和**。 因为守卫们是按顺序站成一排的，而“麻醉弹”只能麻醉 **连续的** k个人，所以我们要找的就是 **所有长度为k的连续子数组中，和最大的那一个**。 下面我用 **C++** 为你提供完整的解决方案。 --- ## 💡 解题思路 1. **滑动窗口法** 使用一个长度为 `k` 的窗口，从数组最左边开始向右滑动。 2. **初始化窗口和** 先计算第一个窗口（前 k 个元素）的和。 3. **滑动更新和** 每次窗口右移一位，减去离开窗口的元素，加上新进入窗口的元素，同时更新最大和。 4. **时间复杂度** 整个数组只需遍历一次，复杂度是 **O(n)**，在 `n ≤ 100000` 范围内非常高效。 --- ## ✅ C++ 代码实现 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); // 加速输入输出 cin.tie(nullptr); int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } // 计算第一个窗口的和 long long windowSum = 0; for (int i = 0; i < k; ++i) { windowSum += a[i]; } long long maxSum = windowSum; // 滑动窗口 for (int i = k; i < n; ++i) { windowSum += a[i] - a[i - k]; // 加入新元素，移除旧元素 maxSum = max(maxSum, windowSum); } cout << maxSum << endl; return 0; } ``` --- ## 🔍 关键点解释 | 代码片段 | 作用 | |---------|------| | `ios::sync_with_stdio(false)` | 关闭 C++ 标准 I/O 与 C 标准 I/O 的同步，加快 `cin/cout` 速度 | | `cin.tie(nullptr)` | 解除 `cin` 与 `cout` 的绑定，避免每次输入前刷新输出缓冲区 | | `windowSum += a[i] - a[i - k]` | 滑动窗口核心更新：减去窗口最左边元素，加上新加入的最右边元素 | | `max(maxSum, windowSum)` | 使用标准库函数更新最大值 | --- ## 🧪 样例验证 输入： ``` 5 3 3 3 4 5 6 ``` 执行过程： - 初始窗口 [3, 3, 4] 和 = 10 - 滑动到 [3, 4, 5] 和 = 12 - 滑动到 [4, 5, 6] 和 = 15 ✅ 输出： ``` 15 ``` --- ## 🛠 开发建议 1. **使用 `long long`** 虽然 `a[i] ≤ 1000`，但 `n` 最大可达 100000，最坏情况下 k=100000，最大和可达 1000 × 100000 = 1e8，在 int 范围内（2^31-1 ≈ 2.1e9），但为了安全起见，建议使用 `long long` 避免溢出。 2. **输入输出优化** 在竞赛或大数据场景下，取消同步和绑定能显著提升性能。如果使用 `printf/scanf` 则无需此操作。 3. **边界情况处理** - 当 `k == n` 时，直接输出所有元素的和。 - 当 `k == 1` 时，问题退化为求数组最大值。 4. **备选方案** - 如果题目改为“不要求连续”，则需要对数组排序后取前 k 个最大值。 - 如果要求“不相邻”的 k 个人，则转化为动态规划问题。 --- ######[AI写代码神器 | 929点数解答 | 2026-05-22 19:55:51]