问题 3121 --1481:最大和

3121: 1481:最大和

题目描述

  对于给定的整数序列A={a1,a2,...,an},找出两个不重合连续子段,使得两子段中所有数字的和最大。我们如下定义函数 d(A):
                     t1     t2 
         d(A) = max{ ∑ai + ∑aj | 1 <= s1 <= t1 < s2 <= t2 <= n } i=s1 j=s2

我们的目标就是求出d(A)。

输入

第一行是一个整数T(≤30),代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是一个整数,代表数据个数据n(2≤n≤50000) ,第二行是n个整数a1,a2,...,an(|ai|≤10000)。

输出

输出一个整数,就是d(A)的值。

样例输入输出

输入#1 复制
1
10
1 -1 2 2 3 -3 4 -4 5 -5
输出#1 复制
13

提示

样例解释:
我们选择 {2,2,3,-3,4} 和 {5}, 就可以得到我们的结果。
数据较多,建议用scanf。

序号 标题 作者 发表时间 费用 订购数 操作