Maximum Circular Subarray Sum

Given a circular array of integers, your task is to find the maximum possible sum of any non-empty subarray. A circular array means that the end of the array wraps around to the beginning. In other words, a subarray can be formed by taking a suffix of the array and a prefix of the array together.

Let \(A\) be an array of \(n\) elements. The answer can be computed as:

[ \text{result} = \max(\text{max_kadane}, \text{total_sum} - \text{min_subarray_sum}) ]

where:

• \(\text{max\_kadane}\) is the maximum subarray sum for the non-circular case (computed by Kadane's algorithm).
• \(\text{total\_sum}\) is the sum of all elements in the array.
• \(\text{min\_subarray\_sum}\) is the minimum subarray sum in the array.

If all numbers are negative, the answer is the maximum element of the array.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(T\), the number of queries. Each query is described in the following format:

• The first line of each query contains an integer \(n\) representing the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the array \(A\).

For example:

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

outputFormat

For each query, output the maximum circular subarray sum on a separate line to standard output (stdout).

For the sample input above, the expected output is:

3
10
-1

## sample

1
4
1 -2 3 -2

3

</p>