Maximizing Sum of Two Non-overlapping Subarrays

You are given a sequence of integers representing the stock prices of a particular stock on consecutive days. Your task is to select two non-overlapping contiguous subarrays such that the sum of their elements is maximized.

For a given array \(A\) of length \(n\), you need to choose two subarrays \(A[i \ldots j]\) and \(A[k \ldots l]\) with \(0 \le i \le j < k \le l < n\) so that the sum of elements in the two subarrays is as large as possible.

Note: The subarrays must not overlap. It is guaranteed that each subarray is non-empty.

inputFormat

The input is given in the following format from standard input:

• The first line contains a single integer \(T\) representing the number of test cases.
• For each test case:
• The first line contains an integer \(n\) (the number of days).
• The second line contains \(n\) space-separated integers representing the stock prices.

outputFormat

For each test case, print a single line containing one integer: the maximum possible sum of the two non-overlapping contiguous subarrays.

## sample

1
5
7 2 5 3 6

23

</p>