2355. 相邻数之和
1000ms
256MB
简单
前缀和与差分
题目描述
松鼠哈利在魔法森林里发现了一排共 $n$ 棵魔法橡树，从左到右整齐地排成一行，编号为 1 到 $n$。每棵橡树上结的黄金橡果数量不同，第 $i$ 棵树上结了 $a_i$ 个橡果。
为了方便采摘，哈利决定只挑选其中**连续的 $m$ 棵树**进行采摘。请你帮哈利计算一下，他能采摘到的最大橡果总数是多少？
输入格式
- 第一行包含两个正整数 $n$ 和 $m$ ($1 \le m \le n \le 100000$)，分别表示橡树的总数和哈利要连续采摘的树木数量。
- 第二行包含 $n$ 个正整数 $a_i$ ($1 \le a_i \le 500$)，表示每棵橡树上的橡果数量，数与数之间用空格隔开。
输出格式
- 输出一行一个整数，表示连续 $m$ 棵树上的最大橡果总数。
样例 1
输入 (Input)
6 3 11 19 9 12 5 20
输出 (Output)
40
样例说明
- **样例解释**：
共有 6 棵树，需要选择连续的 3 棵。
所有连续 3 棵树的和分别为：
- 第 $1 \sim 3$ 棵：$11 + 19 + 9 = 39$
- 第 $2 \sim 4$ 棵：$19 + 9 + 12 = 40$
- 第 $3 \sim 5$ 棵：$9 + 12 + 5 = 26$
- 第 $4 \sim 6$ 棵：$12 + 5 + 20 = 37$
最大值为 40，因此输出 40。
- 对于 $100\%$ 的数据：$1 \le m \le n \le 100000$，$1 \le a_i \le 500$。
- **算法与效率提示**：
由于 $n$ 高达 $100000$，如果对每一个起始位置都循环累加 $m$ 个数，时间复杂度为 $O(n \times m)$。在最坏情况下（例如 $n=100000, m=50000$），计算量会达到 $5 \times 10^9$ 次，必然导致运行超时（TLE）。
我们可以使用**滑动窗口**算法：
1. 先求出前 $m$ 个数的和，作为初始窗口的值。
2. 当窗口向右移动一步时，新的窗口和 = 旧的窗口和 - 移出窗口的元素 + 新移入窗口的元素。
3. 这样每次移动只需进行一次加法和一次减法，时间复杂度为 $O(n)$，可在几毫秒内跑完。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功