滑动窗口求连续k个最大危险值之和（C++实现）

## 😄 解题思路 题目要求计算**连续 k 个守卫**的危险程度总和最大值。 由于数据规模 n ≤ 100000，直接双重循环会超时，需要使用**滑动窗口**技巧： 先计算前 k 个元素的和，然后窗口每次右移一格，减去离开的元素，加上新进入的元素，同时更新最大值。 ## 🧮 算法步骤 1. 读取 n 和 k。 2. 读取数组 a[1] 到 a[n]。 3. 计算初始窗口和：sum = a[1] + a[2] + ... + a[k]。 4. 用循环从 k+1 到 n： - sum = sum - a[i-k] + a[i] - 若 sum > maxSum，更新 maxSum。 5. 输出 maxSum。 ## 💻 C++ 代码实现 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } // 计算初始窗口和 long long sum = 0; for (int i = 0; i < k; i++) { sum += a[i]; } long long maxSum = sum; // 滑动窗口 for (int i = k; i < n; i++) { sum = sum - a[i - k] + a[i]; maxSum = max(maxSum, sum); } cout << maxSum << endl; return 0; } ``` ## 📊 复杂度分析 **时间复杂度**：O(n)，只遍历一次数组。 **空间复杂度**：O(n)，用于存储数组，实际也可优化为 O(1) 但此处用 vector 简洁表示。 **注意**：危险程度总和可能超出 int 范围（最大值 100000 * 1000 = 1e8），使用 long long 安全。 ######[AI问答 | 478点数解答 | 2026-08-29 21:45:15]