Problem1347--PIPI的序列问题Ⅰ

1347: PIPI的序列问题Ⅰ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 588  Solved: 299
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI来考察大家序列处理能力啦。
给定一个长度为n的整数序列A,你需要在A中找到一个长度不大于m的连续子序列,要求这个连续子序列的和最大。 注:可以一个数都不选。
例如:  1, -3, 5, 1, -2, 3
当m=4时,maxsum =  5+1-2+3 = 7
当m=2或m=3时,maxsum = 5+1 = 6

Input

第一行是两个正数n, m  ( n, m ≤ 300000 )
第二行是n个整数Ai,-1e9<=Ai<=1e9.

Output

输出一个整数表示答案。

Sample Input

6 4
1 -3 5 1 -2 3

Sample Output

7

Source/Category

中等