Maximum Circular Subarray Sum

Problem Statement

In the maximum circular subarray sum problem, we have given an array of integers arranged in a circle, find the maximum sum of consecutive numbers in the circular array.

Example

Input

arr[] =  {13, -17, 11, 9, -4, 12, -1}

Output

40

Explanation

Here, sum = 11 + 9 + -4 + 12 + -1 + 13

Input

arr[] = {7, 9, -11, -2, 2, 7, -1, 6}

Output

30

Explanation

Here, sum = 2 + 7 + -1 + 6+ 7 + 9

Input

arr[] = {-17, -2, 1, -10, 2, 3, 7, 9}

Output

21

Explanation

Here, sum = 2 + 3 + 7 + 9

Algorithm for Maximum Circular Subarray Sum

In the maximum circular subarray sum problem, we have two conditions. The first condition is that all the elements are in the contiguous subarray. And the second condition is that some elements from the starting and some elements from the end of the array. For better understanding see the below algorithm-

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

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

3) For case 1, we use the standard Kadane algorithm to find the maximum subarray sum.

4) For case 2, we change wrapping to non-wrapping.

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

Implementation

C++ Program for Maximum Circular Subarray Sum

#include <bits/stdc++.h>
using namespace std;
// Standard Kadane's algorithm to find maximum subarray sum
int kadane(int array[], int n)
{
    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
    int kadane_sum = kadane(array, n);
    //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
    if(wrap_sum > kadane_sum)
    {
      return wrap_sum;
    }
    else
    {
      return kadane_sum;
    }
}
  
//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;
}

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int kadane(int array[], int n)
    {
        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;
    }
    public static int MaxSumCircular(int array[], int n)
    {
        //Max subarray sum in the given array
        int kadane_sum = kadane(array, n);
        //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
        if(wrap_sum > kadane_sum)
        {
          return wrap_sum;
        }
        else
        {
          return kadane_sum;
        }
    } 
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int ans = MaxSumCircular(arr,n);
        System.out.println("Maximum circular subarray sum: " + ans);
    } 
}

8
7 9 -11 -2 2 7 -1 6

Maximum circular subarray sum: 30