Maximum Sum of Circular Subarray

You are given a circular array of n integers. The circular array means that the end of the array connects to its beginning. Your task is to compute the maximum possible sum of a non-empty contiguous subarray. Note that the subarray may wrap around the end of the array.

The problem can be tackled by employing an extended version of Kadane's algorithm. First, run Kadane's algorithm to find the maximum subarray sum in the non-circular case. Then, compute the total sum of the array and run Kadane's algorithm on the inverted array (multiply each element by -1) to find the minimum subarray sum of the original array. The maximum circular subarray sum is then given by:

\( \text{max_circular} = \text{total_sum} + \text{max_inverted} \)

However, if all numbers are negative, the answer is simply the maximum element.

Examples:

• For [1, -2, 3, -2], the result is 3.
• For [5, -3, 5], the result is 10.
• For [1, 2, 3, 4, 5], the result is 15.
• For [-1, -2, -3, -4, -5], the result is -1.

inputFormat

The input consists of two lines:

1. The first line contains a single integer n, the number of elements in the array.
2. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer which is the maximum sum of any contiguous subarray in the given circular array.

## sample

4
1 -2 3 -2

3