Toggle navigation
点码成金编程
F.A.Qs
ProblemSet
Source/Category
Status
Ranklist
Contest
Login
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
数据结构
单调队列