#include <iostream>
#include <algorithm>
using namespace std;
int kadane(int arr[], int n) {
int max_sum = arr[0];
int current_sum = arr[0];
for (int i = 1; i < n; i++) {
current_sum = max(arr[i], current_sum + arr[i]);
max_sum = max(max_sum, current_sum);
}
return max_sum;
}
int maxCircularSum(int arr[], int n) {
int max_kadane = kadane(arr, n);
if (max_kadane < 0) {
return max_kadane;
}
int total_sum = 0;
for (int i = 0; i < n; i++) {
total_sum += arr[i];
arr[i] = -arr[i];
}
int max_wrap = total_sum + kadane(arr, n);
return max(max_kadane, max_wrap);
}
int main() {
int n;
cout << "Enter the size of the array: ";
cin >> n;
int arr[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int max_sum = maxCircularSum(arr, n);
cout << "Maximum circular subarray sum: " << max_sum;
return 0;
}