题目描述

给定一个包含 $n$ 个整数的数组 $v$ 和一个正整数 $k$，请你从中找出长度恰好为 $k$ 的连续子数组，使得该子数组的元素和最大。

你需要输出这个最大和。

输入格式

输入包含两行：

• 第一行包含两个正整数 $n$ 和 $k$，分别表示数组的长度和连续子数组的长度，满足 $1 \leq k \leq n \leq 10^5$。
• 第二行包含 $n$ 个整数 $v_1, v_2, \cdots, v_n$，表示数组的元素，满足 $-10^4 \leq v_i \leq 10^4$。

输出格式

输出一个整数，表示长度为 $k$ 的连续子数组中元素和的最大值。

输入样例

5 3
2 1 5 1 3

输出样例

9

解释: 长度为 3 的连续子数组中，$\{2, 1, 5\}$ 的和为 8，$\{1, 5, 1\}$ 的和为 7，$\{5, 1, 3\}$ 的和为 9。最大和为 9。

输入样例 2

6 2
-1 -2 -3 -4 -5 -6

输出样例 2

-3

解释: 长度为 2 的连续子数组中，$\{-1, -2\}$ 的和为 -3，$\{-2, -3\}$ 的和为 -5，依次类推，最大和为 -3。

数据范围

• $1 \leq n \leq 100,000$
• $1 \leq k \leq n$
• $-10,000 \leq v_i \leq 10,000$

提示

1. 你需要使用滑动窗口算法来实现，时间复杂度为 $O(n)$，否则在最大约 $n = 100,000$ 的情况下，暴力求解会超时。
2. 此题为原创题。