Maximum Gold Collection on Circular Regions

You are given a circular arrangement of regions, each producing a certain amount of gold. Your task is to compute the maximum gold that can be collected by choosing a contiguous sequence of regions, where the sequence may wrap around from the end of the list to the beginning.

Let the gold production values be represented by an array \(a_0, a_1, \dots, a_{M-1}\). The challenge is to determine the maximum sum of a subarray in this circular array. This involves comparing the standard contiguous subarray sum with the sum obtained by wrapping around.

You may use Kadane's algorithm to find the maximum subarray sum, and to compute the wrap-around sum, you can subtract the minimum subarray sum from the total sum of the array. Formally, if \(S\) is the total sum and \(min\) is the minimum subarray sum, then the maximum wrap-around sum is \(S - min\). The final answer is the maximum between the standard subarray sum and the wrap-around sum.

inputFormat

The first line contains an integer \(T\), the number of test cases. Each test case comprises two lines. The first line of each test case contains an integer \(M\), the number of regions. The second line contains \(M\) space-separated integers representing the gold values for each region.

outputFormat

For each test case, output a single line containing one integer — the maximum gold that can be collected from a contiguous sequence of regions.

2
5
1 5 1 3 2
3
2 3 5

12
10