题目描述
给你一个长度为
n
n 的整数序列
\{A_1,A_2,\cdots ,A_n\}
{A1
,A2
,⋯,An
}，要求从中找出一段连续的长度不超过
m
m 的子序列，使得这个序列的和最大。
输入
第一行为两个整数
n,m
n,m；
第二行为
n
n 个用空格分开的整数序列，每个数的绝对值都小于
1000
1000。
输出
仅一个整数，表示连续长度不超过
m
m 的最大子序列和。
样例输入
6 4
1 -3 5 1 -2 3
样例输出
7
提示
数据范围与提示
对于
50\%
50% 的数据，
1\le N,M\le 10^4
1≤N,M≤104；
对于
100\%
100% 的数据，
1\le N,M\le 2\times 10^5
1≤N,M≤2×105。
来源/分类
ybttg DP 单调队列