LeetCode: Maximum Sum Circular Subarray
Tags: datastructures, algorithms, leetcode, dp
Published: 2020-05-19 15:33:24

---
title: LeetCode: Maximum Sum Circular Subarray
published: true
description: Day 15
tags: datastructures, algorithms, leetcode, DP
series: LeetCode May Challenge
---

### 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

```c++
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.

```c++
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.



```c++
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:

```c++
 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:

```c++
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.

```c++
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)