Problem description:

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.)

1
2
3
4
5
Example 1:

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

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

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

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

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

Note:

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

Solution:

This is a followup question of 53. Maximum Subarray. We can use a similar idea to solve it.
The idea is to remove the biggest negative sum in the array. Then the rest of the elements are the maximum sum in a continuous way.

Idea:
The result will have the following two different cases.

For example:
[2,3,-6,-7,4,5]
total sum= 1: 2+3+4+5= 14, -6+(-7)= -13
that is to say, if we can find the elements we want to remove, then we can get the maximum continuous sum.

  1. Calculate the maximum continuous sum, nocircle, of the original array. If the nocircle is negative, it means all the elements in the array is negative. Therefore, just return the largest negative element. Which is -1 in the above example.
  2. Sum up the array, and multiply each element with -1 in the mean time. By doing this, we can use the same help function to get the smallest continuous sum in the original array, which is [6,7] in above example.
  3. Compare the nocircle and circle, return the maximum one.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int nocircle= help(A), sum= 0;
        if(nocircle < 0)
            return nocircle;
        
        vector<int> tmp= A;
        for(auto &n: tmp){
            sum+= n;
            n*= -1;
        }   
        
        int circle= sum+ help(tmp);
        return max(circle, nocircle);
    }
    int help(vector<int>& A){
        int max_endhere= 0, max_sofar= INT_MIN;
        for(int i= 0; i< A.size(); i++){
            if(max_endhere < 0)
                max_endhere= A[i];
            else
                max_endhere+= A[i];
            
            max_sofar= max(max_sofar, max_endhere);
        }
        return max_sofar;
    }
};

Solution One pass:

We can further optimize the code with four variables to record the current minimum/maximum, all tim minimum/maximum as shown below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int total = 0, maxSum = -30000, curMax = 0, minSum = 30000, curMin = 0;
        for (int a : A) {
            curMax = max(curMax + a, a);
            maxSum = max(maxSum, curMax);
            curMin = min(curMin + a, a);
            minSum = min(minSum, curMin);
            total += a;
        }
        return maxSum > 0 ? max(maxSum, total - minSum) : maxSum;
    }
};

time complexity: $O(n)$
space complexity: $O(1)$
reference:
https://www.geeksforgeeks.org/maximum-contiguous-circular-sum/
https://goo.gl/na2uyB