Description

For a given integer sequence $A={a_1, a_2,..., a_n}$, find two non-overlapping contiguous subsequences such that the sum of all numbers in these two subsequences is maximized. We define the function as follows: Our goal is to compute $d(A)$.

Input Format

The first line contains an integer $T(≤30)$, representing the number of test cases.
This is followed by $T$ test cases.
For each test case:

• The first line contains an integer $n(2≤n≤50000)$, representing the length of the sequence.
• The second line contains $n$ integers $a\_1, a\_2, ..., a\_n(|a\_i| ≤ 10000)$.

Output Format

Output an integer, which is the value of $d(A)$.

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

13

Hint

This problem is essentially about finding the maximum subarray sum. The sample cases are ${2,2,3,-3,4}$ and ${5}$. You can search for "POJ 2479 Maximum sum" on Baidu to find extensive classic explanations on the maximum subarray sum problem. Note that an $O(n^2)$ algorithm will result in a Time Limit Exceeded error for this problem, so an $O(n)$ algorithm must be used.