Maximum Sum Circular Subarray

Posted in

Maximum Sum Circular Subarray
vinaykhatri

Vinay Khatri
Last updated on March 28, 2024

    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:

    Leave a Comment on this Post

    0 Comments