6651: Maximum sum
[Creator : ]
Description
Given a set of $n$ integers: $A=\{a_1, a_2,…, a_n\}$, we define a function d(A) as below:
$d(A)=\text{max}(\sum^{t_1}_{i=s_1}a_i+\sum^{t_2}_{j=s_2}a_j\ |\ 1 \leq s_1 \leq t_1<s_2 \leq t_2 \leq n)$
Your task is to calculate d(A).
$d(A)=\text{max}(\sum^{t_1}_{i=s_1}a_i+\sum^{t_2}_{j=s_2}a_j\ |\ 1 \leq s_1 \leq t_1<s_2 \leq t_2 \leq n)$
Your task is to calculate d(A).
Input
The input consists of $T\ (T \leq 30)$ test cases. The number of test cases (T) is given in the first line of the input.
Each test case contains two lines.
The first line is an integer $n\ (2\leq n \leq 50,000)$.
The second line contains $n$ integers: $a_1, a_2, …, a_n.\ (|a_i| <= 10,000)$.
There is an empty line after each case.
Each test case contains two lines.
The first line is an integer $n\ (2\leq n \leq 50,000)$.
The second line contains $n$ integers: $a_1, a_2, …, a_n.\ (|a_i| <= 10,000)$.
There is an empty line after each case.
Output
Print exactly one line for each test case. The line should contain the integer d(A).
Sample 1 Input
1
10
1 -1 2 2 3 -3 4 -4 5 -5
Sample 1 Output
13
we choose {2,2,3,-3,4} and {5}, then we can get the answer.
Sample 2 Input
1
2
1 -3
Sample 2 Output
-2
Sample 3 Input
1
5
5 4 -1 7 8
Sample 3 Output
24
HINT
题目来源：OpenJudge。