4320: §2 9 Maximum sum
[Creator : ]
Description
对于给定的整数序列 $A=\{a_1,a_2,...,a_n\}$，找出两个不重合连续子段，使得两子段中所有数字的和最大。我们如下定义函数 $d(A)$：
我们的目标就是求出 $d(A)$。
我们的目标就是求出 $d(A)$。
Input
第一行是一个整数 $T(T≤30)$，代表一共有多少组数据。
接下来是 $T$ 组数据。
每组数据的第一行是一个整数，代表数据个数据 $n(2≤n≤50000)$，第二行是 $n$ 个整数 $a_1,a_2,...,a_n(|a_i|≤10000)$。
接下来是 $T$ 组数据。
每组数据的第一行是一个整数，代表数据个数据 $n(2≤n≤50000)$，第二行是 $n$ 个整数 $a_1,a_2,...,a_n(|a_i|≤10000)$。
Output
输出一个整数，就是 $d(A)$ 的值。
Sample 1 Input
1
10
1 -1 2 2 3 -3 4 -4 5 -5
Sample 1 Output
13