Kadane’s Algorithm: Maximum Circular Subarray Sum

Problem Statement:

You are given a circular array, you need to find the Maximum sum.

A circular array allows wrapping from the end to the beginning.

Example:

Input: [3, -1, -2, 2]
Output: 5

Explanation:

Here the circular subarray will be [3, -1, -2, 2, 3, -1, -2]
So the max subarray sum will be [2, 3] = 

Solution Explanation:

Solution is very simple.

We need to run Kadane’s Algorithm 2 times.

One time for the normal array and one time for circular array.

Then take the max result of the 2 runs and return the result.

This is because, the max subarray sum can be in the noraml array or in the circular array.

We know how to calculate the normal array.

We will see how to calculate for Circular array:

To find the Maximum Subarray Sum for circular array, follow the below steps:

1. We can find the result by using the total sum of the array minum the sum of subarray in the middle.

2. So to maximum the circular sub array sum, we need to minimize the subarray sum

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
using namespace std;

int solution(vector<int> &arr) 
{

    int totalSum = 0;
    int currMaxSum = 0;
    int currMinSum = 0;
    int maxSum = arr[0];
    int minSum = arr[0];

    for (int i = 0; i < arr.size(); i++) 
    {
        currMaxSum = max(currMaxSum + arr[i], arr[i]);
        maxSum = max(maxSum, currMaxSum);

        currMinSum = min(currMinSum + arr[i], arr[i]);
        minSum = min(minSum, currMinSum);

        totalSum = totalSum + arr[i];
    }

    int normalSum = maxSum;
    int circularSum = totalSum - minSum;

    if (minSum == totalSum)
        return normalSum;

    return max(normalSum, circularSum);
}

int main() 
{
    vector<int> arr = {3, -1, -2, 2};
    cout << solution(arr);
}

Output

5