Circular Subarray Maximum Sum

You are given an array of integers arranged in a circular sequence. Your task is to find the maximum sum of any subarray, where the subarray can be chosen in the usual contiguous manner or can be circular (wrapping from the end of the array to the beginning).

This problem can be formulated as follows: For an array \(A = [a_1, a_2, \dots, a_n]\), find the maximum value between:

[ \max(\text{maxSubarray}(A),, \text{totalSum}(A)-\text{minSubarray}(A)) ]

Note: If all numbers in the array are negative, then the answer is simply the maximum number (i.e. the least negative value).

Example:

Input: [1, -2, 3, -2, 5]
Output: 7 
Explanation: The maximum subarray sum considering wrap-around is 7.

inputFormat

The first line contains an integer \(T\) that denotes the number of test cases.

For each test case:

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

outputFormat

For each test case, output a single line containing the maximum subarray sum.

## sample

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

7
16

</p>