Maximum Sum Circular Subarray

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

People are also reading:

• Construct a tree from Inorder and Level order traversals
• Program to Rotate an Array
• Print a given matrix in spiral form
• Rearrange an array such that arr[i] = i
• The Stock Span Problem
• Find maximum of minimum for every window size in a given array
• Diameter of a Binary Tree
• Clone a Singly Linked List
• How to find and remove loops in a Linked List?
• Find a Pair with the Given Sum in an Array