Maximum Sum Circular Subarray

By | October 29, 2021

Problem

Given a circular integer array `nums` of length `n`, return the maximum possible sum of a non-empty subarray of `nums`.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of `nums[i]` is `nums[(i + 1) % n]` and the previous element of `nums[i]` is `nums[(i - 1 + n) % n]`.

Please note that an index of the original array can’t come twice in the resultant subarray.

Approach

The maximum subarray can be in two circumstances. The sub-array will be either not circular (simply one subarray of the original array) or circular (will wrap around from the  starting).

In the first case, use the procedure of Kadane to get the largest subarray sum.

In the second situation, the minimal subarray sum may be found and it can be reduced from the total sum of the original array. That, of course, would give us the maximum sum for the remaining subarray.

Based on the above two cases, return the maximum value.

But there is a case of the margin. If all elements are negative, return the largest of them.

C++ Programming

```#include<bits/stdc++.h>
using namespace std;

int maxSubarraySumCircular(vector<int>& nums) {
int total = accumulate(nums.begin(), nums.end(), 0);
int n = nums.size();
vector<int>nums1=nums;
sort(nums1.begin(), nums1.end());

if(nums1[0]<0 && nums1[n-1]<0){   //if all elements are negative
return nums1[n-1];
}
int sum0 = 0;
int ans0 = 0;
for(int i=0; i<n; i++){    //kadane's algorithm for original array
sum0 += nums[i];
sum0 = max(sum0,0);
ans0 = max(ans0,sum0);
}
for(int i=0; i<n; i++){       //change sign of each number
nums[i]*=-1;
}
int sum = 0;
int ans = 0;
for(int i=0; i<n; i++) //kadane's algorithm after changing signs
{
sum += nums[i];
sum = max(sum,0);
ans = max(ans,sum);
}
return max(total-(-1*ans), ans0);
}
int main(){
vector<int>v{1, 2, -1, 77};
cout<<maxSubarraySumCircular(v);
}```

Output

`80`

C Programming

```#include <stdio.h>
int findMaxSubarray(int a[], int n)
{
int res = 0, sum = 0;
int i;
for (i = 0; i < n; i++) {
sum = sum + a[i];
if (sum < 0)
sum = 0;
if (res < sum)
res = sum;
}
return res;
}

int maxSubarraySum(int a[], int n)
{
//get the maximum sum using standard findMaxSubarray'
int ans0 = findMaxSubarray(a, n);

//find the maximum sum that includes
// corner elements.
int ans = 0, i;
for (i = 0; i < n; i++) {
ans += a[i]; // Calculate array-sum
a[i] = -a[i]; // invert the array (change sign)
}

// max sum with corner elements will be:
// array-sum - (-max subarray sum of inverted array)
ans = ans + findMaxSubarray(a, n);

return (ans > ans0) ? ans : ans0;
}

int main()
{
int a[] = {1, 2, -1, 77};
int n = sizeof(a) / sizeof(a[0]);
printf("Maximum sum is %d",
maxSubarraySum(a, n));
}```

Output

`Maximum sum is 80`

Python Programming

```def maxSubarray(a):
n = len(a)
ans = 0
sum = 0
for i in range(0, n):
sum = sum + a[i]
if (sum < 0):
sum = 0
if (ans < sum):
ans = sum
return ans

def maxSubarraySumCircular(a):

n = len(a)

# get the maximum sum using standard maxSubarray
ans0 = maxSubarray(a)

# Now find the maximum sum that includes corner
# elements.
ans = 0
for i in range(0, n):
ans += a[i]
a[i] = -a[i]

# Max sum with corner elements will be:
# array-sum - (-max subarray sum of inverted array)
ans = ans + maxSubarray(a)

if ans > ans0:
return ans
else:
return ans0

a = [1,2,-1,77]
print ("Maximum sum is", maxSubarraySumCircular(a))```

Output

`Maximum sum is 80`