LeetCode: Maximum Sum Circular Subarray

Problem statement

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:

Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:

Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:

Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:

Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1

Note:

1. -30000 <= A[i] <= 30000
2. 1 <= A.length <= 30000

Solution

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        return max(FindMaxSubarray(A), FindCircularMaxSubarray(A));
    }

    int FindMaxSubarray(vector <int>& A)
    {
        int maximumTill = 0, maximum = numeric_limits<int>::min();
        for(int a:A)
        {
            /* 
            We have two options
               1. Start a new subarray
               2. Continue the previous subarray
            */ 
            maximumTill = max(a, a+maximumTill);
            maximum = max(maximum, maximumTill);
        }
        return maximum;
    }

    int FindCircularMaxSubarray(vector <int>& A)
    {
         // Maximum subarray sum starts at index 0 and ends at or before index i
        vector<int>maximumBegin;
        int sum = A.front();
        maximumBegin.emplace_back(sum);
        for(int i=1;i<A.size();i++)
        {
            sum += A[i];
            maximumBegin.emplace_back(max(maximumBegin.back(),sum));
        }


        // Maximum subarray sum starts at index i+1 and ends at the last element
        vector<int> maximumEnd(A.size());
        maximumEnd.back() = 0;
        sum = 0;
        for(int i=A.size()-2;i>=0;--i)
        {
            sum+= A[i+1];
            maximumEnd[i] = max(maximumEnd[i+1],sum);
        }

        // calculates the maximum subarray which is circular

        int circularMax = INT_MIN;
        for(int i=0;i<A.size();i++)
        {
            circularMax = max(circularMax, maximumBegin[i]+maximumEnd[i]);
        }
        return circularMax;
    }
};

Solution Thought Process

First intuition is, the maximum circular subarray can be two things:

• It can be a regular subarray without circularity. Take this array for example:

arr  [-1,  -2,  -3,  4,  5,  6,  -1]
idx    0    1    2   3   4   5    6

Here the answer is 9, and the subarray is the index [3,4]

• It can be circular, meaning that the subarray takes all the element till the end of the array and takes some more element from the front of the array, because we have given circular access. Take this array for example:

arr  [ 1,  -2,  -3,  7, -2,  7]
idx    0    1    2   3   4   5

Here the answer is 13, we have to take [3,5] and [0] both as a solution space giving us the maximum circular subarray.

We find out those two elements and take the max of them. That is our answer.

int maxSubarraySumCircular(vector<int>& A) {
   return max(FindMaxSubarray(A), FindCircularMaxSubarray(A));
}

First let's work on the FindMaxSubarray part. The algorithm is, on each index, we make two decisions -

• We start a new subarray with this index element.
• We continue the previous subarray with this index element.

After that we get the maximum returned from that function.

int FindMaxSubarray(vector <int>& A)
{
    int maximumTill = 0, maximum = numeric_limits<int>::min();
    for(int a:A)
    {
        /* 
            We have two options
               1. Start a new subarray - Taking a
               2. Continue the previous subarray - Taking a+maximumTill
        */ 
        maximumTill = max(a, a+maximumTill);
        maximum = max(maximum, maximumTill);
    }
    return maximum;
}

Let's work on the FindCircularMaxSubarray function next. We are assuming that the circular Let's check out it's intuition. Let's consider this array with elements:

a(0)   a(1)  a(2)  a(3)  a(4)  ..... a(i) ......  a(n-2)   a(n-1) 

For every index i we calculate two things:

• Maximum subarray sum starts at index 0 and ends at or before index i

• Maximum subarray sum starts at index i+1 and ends at the last element

If we have those two values, we can iterate over every i , add those two values and find out the maximum value.

Why?

Let's think about the circular subarray. If the maximum subarray is not in the middle of the array, then it should have some elements from the index 0 to i, not necessarily all the elements. Also the subarray should have some elements from the n-1 to the i+1 element, not necessarily all the elements. So we take those two sums for the i th index and take the maximum value over all index i.

For finding maximum subarray sum starts at index 0 and ends at or before index i, we make use of this code:

 vector<int>maximumBegin;
 int sum = A.front();
 maximumBegin.emplace_back(sum);
 for(int i=1;i<A.size();i++)
 {
     sum += A[i];
     maximumBegin.emplace_back(max(maximumBegin.back(),sum));
 }

Applying this algorithm, we get the following maximumBegin vector:

arr           [ 1,  -2,  -3,  7, -2,  7]
idx             0    1    2   3   4   5
sum             1   -1   -4   3   1   8             
maximumBegin    1    1    1   3   3   8

All the subarray sum starting at 0 and ends at or before index i gets stored at maximumBegin vector.

For finding maximum subarray sum starts at index i+1 and ends at the last element we make use of this code:

vector<int> maximumEnd(A.size());
maximumEnd.back() = 0;
sum = 0;
for(int i=A.size()-2;i>=0;--i)
{
    sum+= A[i+1];
    maximumEnd[i] = max(maximumEnd[i+1],sum);
}

Applying this algorithm, we get the following maximumBegin vector:

arr           [ 1,  -2,  -3,  7, -2,  7]
idx             0    1    2   3   4   5
sum             7    9   12   5   7   0
maximumEnd     12   12   12   7   7   0         

All the subarray sum starts at index i+1 and ends at the last element gets stored at maximumEnd vector.

Now we iterate over all the indices i and get the circular maximum.

int circularMax = INT_MIN;
for(int i=0;i<A.size();i++)
{
    circularMax = max(circularMax, maximumBegin[i]+maximumEnd[i]);
}
return circularMax;

Let's see the function in action with example:

arr           [ 1,  -2,  -3,  7, -2,  7]
idx             0    1    2   3   4   5           
maximumBegin    1    1    1   3   3   8
maximumEnd     12   12   12   7   7   0
circularSum    13   13   13  10  10   8

From the array, we can see the maximum circular sum is 13, so we return 13 as our circularMax .

This ends our FindCircularMaxSubarray function. Next we just compare the two functions FindCircularMaxSubarray and FindMaxSubarray, and return the maximum value as our result. From the FindMaxSubarray function, we get the result as 12, from the FindCircularMaxSubarray we get the result as 13. So 13 is our answer.

Complexity

Time Complexity: O(n)

Space Complexity: O(n)