Uber

2020-05-15

## 918. Maximum Sum Circular Subarray

### Question:

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

Similar to LeetCode Question 53, using Kadane’s algorithm to find the Maximum and Minimum sum of the array. In addition, we also need to find the sum of values for the array. Based on different cases, we use different way to find the maximum sum.

1. `[1, 2, 3]` (Max: 5, Min: 1, Total: 6)The result is the Maximum of the array.
2. `[-3, -2, -1]` (Max: -1, Min: -6, Total: -6) The result is the Maximum of the array.
3. `[5, -3, 5]` (Max: 7, Min: -3, Total: 7) The result is the (Total - Minimum) of the array.

Time: O(N)
Space: O(1)

``````class Solution {
public int maxSubarraySumCircular(int[] A) {
int prevMax = A;
int prevMin = A;
int total = A;
int globalMax = A;
int globalMin = A;

for (int i = 1; i < A.length; i++) {
int curr = A[i];
prevMax = Math.max(curr, prevMax + curr);
globalMax = Math.max(prevMax, globalMax);
prevMin = Math.min(curr, prevMin + curr);
globalMin = Math.min(prevMin, globalMin);
total += curr;
}

// Special case if all the numbers are negative
if (total - globalMin == 0) {
return globalMax;
}

return Math.max(globalMax, total - globalMin);
}
}
``````