Maximum Sum Circular Subarray Leet Code with C++, Python, Java, and JavaScript Solutions

Solution Explanation:

We iterate through the array and keep track of the maximum sum subarray seen so far, the maximum sum subarray ending at the current element, the minimum sum subarray seen so far, and the minimum sum subarray ending at the current element. The maximum sum subarray of a circular array is either the maximum subarray of the non-circular array or the total sum of the array minus the minimum subarray of the non-circular array.

C++ :

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;
    }
};

Java:

class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int total = 0, maxSum = Integer.MIN_VALUE, curMax = 0, minSum = Integer.MAX_VALUE, curMin = 0;
        for (int a : A) {
            curMax = Math.max(curMax + a, a);
            maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(curMin + a, a);
            minSum = Math.min(minSum, curMin);
            total += a;
        }
        return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    }
}

Python:

class Solution:
    def maxSubarraySumCircular(self, A: List[int]) -> int:
        total, maxSum, curMax, minSum, curMin = 0, float('-inf'), 0, float('inf'), 0
        for a in A:
            curMax = max(curMax + a, a)
             maxSum = max(maxSum, curMax)
             curMin = min(curMin + a, a)
             minSum = min(minSum, curMin)
             total += a
     return max(maxSum, total - minSum) if maxSum > 0 else maxSum

Javascript:

Explanation:

This solution is similar to the previous solutions in C++ and Java. We iterate through the input array, keeping track of the maximum sum subarray seen so far, the maximum sum subarray ending at the current element, the minimum sum subarray seen so far, and the minimum sum subarray ending at the current element.

The maximum sum subarray of a circular array is either the maximum subarray of the non-circular array or the total sum of the array minus the minimum subarray of the non-circular array.

We use the Math.max() and Math.min() functions to find the maximum and minimum sums, respectively. The -Infinity and Infinity values are used as initial values for the maximum and minimum sums, respectively, to ensure that any value in the input array will be larger or smaller, respectively.

var maxSubarraySumCircular = function(A) {
    let total = 0;
    let maxSum = -Infinity;
    let curMax = 0;
    let minSum = Infinity;
    let curMin = 0;
    
    for (let i = 0; i < A.length; i++) {
        curMax = Math.max(curMax + A[i], A[i]);
        maxSum = Math.max(maxSum, curMax);
        curMin = Math.min(curMin + A[i], A[i]);
        minSum = Math.min(minSum, curMin);
        total += A[i];
    }
    return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
};

Dart

int maxSubarraySumCircular(List<int> A) {
    int total = 0;
    int maxSum = -1000000000;
    int curMax = 0;
    int minSum = 1000000000;
    int curMin = 0;
    for (int a in 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;
}