HZNUOJ

岳墓栖霞

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:1081     AC:365     Score:86.48

Description

岳墓栖霞是西湖著名景点之一。岳墓背靠栖霞岭,位于苏堤北面,每当夕阳西下时,岳墓上便有了一道道霞光,非常绚美,因而得名"岳墓栖霞"。

一天,WW同学远赴西湖岳墓观赏晚霞。晚霞很美,但总有人无心美景,CSX就是其中一位。他竟然在一片美丽的晚霞中研究题目。WW走近一看,题目是这样的,给定序列$a_1、a_2、a_3$……$a_n$,求这个序列中连续子序列的最大和。例如,给定(6,-1,5,4,-7),那么最大和为6+(-1)+5+4=14。

Input

第一行给出整数T($T \lt 10$),这意味着有T组测试数据

对于每组测试样例,第一行给出一个整数n($n \lt 1000$),代表该序列有n个整数,第二行给出n个整数。

Output

对于每组测试样例,输出连续子序列的最大和

Samples

input
2 5 1 2 3 4 -5 7 0 -1 99999 -1 0 0 0
output
10 99999
input
3 5 -1 2 4 -7 9 10 1 9 8 -2 -2 3 4 -1 -2 9 7 999 -99 -232 997 -23 32 333
output
9 27 2007

Hint

连续子序列为该序列中下标连续的项

例如,对序列 $[a_1, a_2, a_3, a_4, a_5]$

连续子序列可以是 $[a_1, a_2, a_3]$

但不可以是$[a_1, a_2, a_4, a_5]$

Author

SHI, JUNWEI