# Maximum circular subarray sum

## In the given array of integers arranged in a circle, find the maximum sum of consecutive numbers in the circular array.

### Example

a) Input array: [13, -17, 11, 9, -4, 12, -1]
Output: 40
Here, sum = 11 + 9 + -4 + 12 + -1 + 13

b) Input array: [7, 9, -11, -2, 2, 7, -1,6]
Output: 30
Here, sum = 2 + 7 + -1 + 6+ 7 + 9

c) Input array: [-17, -2, 1, -10, 2, 3, 7, 9]
Output: 21
Here, sum = 2 + 3 + 7 + 9

## Algorithm

Time complexity: O(n)

Two cases of maximum sum:

1) Elements which contribute to the maximum sum are arranged such that no wrapping is there. Like in Example (c)

2) Elements which contribute to the maximum sum are arranged such that wrapping is there. Like in Example (a,b).

a. For case 1, we use standard Kadane algorithm to find maximum subarray sum.
b.    For case 2, we change wrapping to non-wrapping.

1) We store the sum of all the elements in the array.
2) Change the sign of all the elements while adding into the sum.
3) For the new array with inverted signs again apply kadane algorithm to this new array.
5) Compare this sum with initial kadane sum (before inverting the signs) return maximum among them.

## C++ Program

``````#include <bits/stdc++.h>

using namespace std;

// Standard Kadane's algorithm to find maximum subarray sum
{
int max_so_far = 0, max_ending_here = 0;
for (int i = 0; i < n; i++)
{
max_ending_here = max_ending_here + array[i];
if (max_ending_here < 0)
max_ending_here = 0;
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}

//function to find maximum circular subarray sum
int MaxSumCircular(int array[], int n)
{
//Max subarray sum in the given array
//wrap_sum is sum of all elements in the array
int wrap_sum = 0;
//find sum of all elements in the array
//invert signs of all elements in the array
for (int i=0; i<n; i++)
{
wrap_sum += array[i];
array[i] = -array[i];
}
//update wrap_sum by add to new Max subarray sum
wrap_sum = wrap_sum + kadane(array, n);
//Return the maximum of them
{
return wrap_sum;
}
else
{
}
}

//Main function
int main()
{
int input_array[] = {7, 9, -11, -2, 2, 7, -1, 6};
int size = sizeof(input_array)/sizeof(int);
cout<<"Maximum circular subarray sum: "<<MaxSumCircular(input_array,size)<<endl;
return 0;
}``````

Scroll to Top