4934 - 单调队列:【 例 2】最大连续和

给你一个长度为 n 的整数序列 {A1,A2,⋯,An},要求从中找出一段连续的长度不超过 m 的子序列,使得这个序列的和最大。

输入

第一行为两个整数 n,m; 第二行为 n 个用空格分开的整数序列,每个数的绝对值都小于 1000。

输出

仅一个整数,表示连续长度不超过 m 的最大子序列和。

样例

输入

6 4
1 -3 5 1 -2 3

输出

7

提示

数据范围与提示:

对于 50% 的数据,1≤N,M≤10^4 ;

对于 100% 的数据,1≤N,M≤2×10^5 。

时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题