最大连续子串和问题

2013年11月28日1,2680

题目描述

给定有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

来源

dp做法

 

 

还有O(n)的