1085: 最大子段和

Memory Limit：256 MB Time Limit：0.500 S Judge Style：Text Compare Creator：
Submit：59 Solved：22

Description

输入若干个整数，有正有负，要求用动态规划算法计算最大子段和，并输出这个和。注意子段为一段连续的数，同时规定全是负数的子段其和为0。

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

第一行为一个整数M，代表有M组测试数据。
随后每组测试数据的第一行为N，代表该组数据有N个数。(0接下来一行给出用空格隔开的这N个整数。

n取值范围不超过50000

Output

每组测试数据输出一行，即最大子段和。

Sample Input Copy 

1
8
-2 10 8 -4 7 5 -29 10

Sample Output Copy 

26

Source/Category