最大子段和

题目描述

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

输入说明

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

输出说明

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

样例

输入

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

输出

26

提示

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