Sum of Two Subarrays

Problem Description

Given an integer sequence $A=\{a_1, a_2, \dots, a_n\}$, find two non-overlapping contiguous subarrays such that the sum of all numbers in the two subarrays is maximized. Define $d(A)$ as:

$$d(A) = \max_{1 \le s_1 \le t_1 \le s_2 \le t_2 \le n} \left\{ \sum_{i=s_1}^{t_1} a_i + \sum_{j=s_2}^{t_2} a_j \right\}$$

Your task is to compute $d(A)$.

Input Format

The first line is an integer $T$ ($T \le 30$), the number of test cases.

Each test case: the first line is an integer $n$ ($2 \le n \le 50000$); the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($|a_i| \le 10000$).

Output Format

A single integer: the value of $d(A)$.

Sample Input

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

Sample Output

13

Hint

This is the maximum subarray sum problem. In the sample, take $\{2,2,3,-3,4\}$ and $\{5\}$. An $O(n^2)$ algorithm will time out; you must use an $O(n)$ algorithm.

Limitation

1 s, 1024 KiB for each test case.