10095: 最大子段和

内存限制：256 MB 时间限制：1.000 S 提交：24 解决：9
评测方式：文本比较 命题人：

题目描述

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

输入

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

输出

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

样例输入 复制 

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

样例输出 复制 

26

提示

1<m<=10

1<=n<=100000