最大连续子段和问题

2013年11月8日1,5060

题目描述

给定有n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列连续的子段和的最大值。如果该序列的所有元素都是负整数时定义其最大子段和为0。例如,当(a1,a2,a3,a4,a5)=(-5,11,-4,13,-4-2)时,最大子段和为11+(-4)+13=20。

输入

输入数据有T组测试数据。测试数据的数目 (T)在输入的第一行给出。每组测试数据有两行:第一行整数个数N,第二行为N个整数,每个整数之间用一空格隔开。

输出

对于每组数据,输出一行,为最大连续子段和。

样例输入

1 6 -5 11 -4 13 -4 -2

样例输出

20

提示

 

 1<=T<=20

1<=N<=100000

N个整数的范围为-1000到1000

 

代码