Problem 66: Maximum Circular Subarray Sum

Problem Statement: Given a circular array of integers, find the maximum possible sum of a contiguous subarray. The subarray may wrap around the end of the array.

Input

The first line contains an integer n. The second line contains n space-separated integers.

Output

Print the maximum circular subarray sum.

Examples


Input:
5
8 -1 3 4 -5

Output:
15

Solution Explanation

Use Kadane's algorithm to find the maximum subarray sum normally and also compute the total sum minus the minimum subarray sum. The answer is the maximum of the two, with care for all negative cases.

Solution in C++


#include 
#include 
#include 
using namespace std;

int kadane(const vector& a){
    int best = a[0], cur = a[0];
    for(int i = 1; i < a.size(); i++){
        cur = max(a[i], cur + a[i]);
        best = max(best, cur);
    }
    return best;
}

int main(){
    int n; 
    cin >> n;
    vector a(n);
    int total = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        total += a[i];
    }
    int max_kadane = kadane(a);
    int min_cur = a[0], min_kadane = a[0];
    for(int i = 1; i < n; i++){
        min_cur = min(a[i], min_cur + a[i]);
        min_kadane = min(min_kadane, min_cur);
    }
    int ans = (total - min_kadane == 0) ? max_kadane : max(max_kadane, total - min_kadane);
    cout << ans << "\n";
    return 0;
}