Home => ProblemSet => 3.4-16:最大子序和
Problem1947--3.4-16:最大子序和

1947: 3.4-16:最大子序和

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

一个长度为n的整数序列,从中找出一段不超过m的连续子序列,使得整个序列的和最大。
例如:  1, -3, 5, 1, -2, 3
当m=4时,sum =  5+1-2+3 = 7
当m=2或m=3时,sum = 5+1 = 6

Input

第一个行一个正整数T,表示多测试用例;
每个测试用例:
第一行是两个正数n, m  ( n, m ≤ 300000 );
第二行是n个整数;

Output

每个测试用例输出一行:一个正整数,表示这n个数的最大子序和长度

Sample Input Copy

1
6 4
1 -3 5 1 -2 3

Sample Output Copy

7

Source/Category