Maximum Thrill Ride

You are given an integer N representing the number of stations and an array of N integers, where each integer denotes the thrill level at a corresponding station. The stations are arranged in a circular fashion, meaning that after the last station, the ride continues back to the first station.

Your task is to determine the maximum thrill level a rider can achieve by riding along a contiguous segment of stations. This contiguous segment may wrap around from the end of the array back to the beginning. In other words, you need to find the maximum sum of a subarray, with the added twist that the subarray can be circular.

A common approach is to use Kadane's algorithm to compute the maximum subarray sum for the non-circular case. For the circular case, you can compute the total sum of the array and subtract the minimum contiguous subarray sum. The final answer is the maximum between the direct maximum subarray sum and this circular sum. Mathematically, if we denote the array as \(a_0, a_1, \dots, a_{N-1}\), then the maximum circular subarray sum is given by:

[ \text{max_circular} = \text{total} + \min_{\text{subarray}} (\text{sum of subarray}) ]

Note: If all values are negative, the answer is the maximum element in the array.

inputFormat

The input consists of two lines:

• The first line contains a single integer N, the number of stations.
• The second line contains N space-separated integers, representing the thrill levels at each station.

outputFormat

Output a single integer representing the maximum thrill level achievable.

5
1 -2 3 -1 2

5