10792: 最大子段和

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

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

Input

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

Output

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

Sample Input Copy

1<br/>8<br/>-2 10 8 -4 7 5 -29 10<br/>

Sample Output Copy

26

HINT

如果不用动态规划算法而用穷举法,则会超时。