Maximum Sum Circular Subarray

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

-30000 <= A[i] <= 30000
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, 2, 3] (Max: 5, Min: 1, Total: 6)The result is the Maximum of the array.
[-3, -2, -1] (Max: -1, Min: -6, Total: -6) The result is the Maximum of the array.
[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[0];
        int prevMin = A[0];
        int total = A[0];
        int globalMax = A[0];
        int globalMin = A[0];
        
        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);
    }
}