Maximum sum

题目描述

对于给定的整数序列 $A=\{a_1,a_2,\dots,a_n\}$，找出两个不重合的连续子段，使得两子段中所有数字的和最大。本题即求 $d(A)$ 的值。

输入

第一行是一个整数 $T$（$T\le 30$），代表一共有多少组数据。接下来是 $T$ 组数据。每组数据的第一行是一个整数，代表数据的个数 $n$（$2\le n\le 50000$），第二行是 $n$ 个整数 $a_1,a_2,\dots,a_n$（$|a_i|\le 10000$）。

输出

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

样例输入

1
10
1 -1 2 2 3 -3 4 -4 5 -5

样例输出

13