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;
}