Leetcode 918. Maximum Sum Circular Subarray

Problem Explanation:

The problem requires to calculate the maximum sum of a subarray considering it as a circular array. A circular array means the end of the array connects to the beginning of the array. So we can cross from the end of the array to the beginning when calculating maximum subarray.

Additionally, it's stated that a subarray may only include each element of the fixed buffer A at most once, meaning we cannot select an element more than once to calculate maximum sum.

For example, if the input is [5,-3,5], the maximum sum would be 10 (5 + 5 = 10), here we selected both '5's but didn't select '-3'. Even though the array is circular, we skip '-3' to meet the condition of getting maximum sum from subarray.

Solution Explanation:

The solution uses the approach of Kadane's algorithm, which is used for finding the maximum/minimum sum of a subarray in the array. It maintains the maximum/minimum subarray sum end at each position and the maximum/minimum sum can be easily found then.

But as this problem is a variant of the problem, to handle the circular condition, we need an extra step. The maximum subarray sum is either the maximum subarray sum of the array or the total sum of the array minus the minimum subarray sum of the array.

Note: If max subarray sum is less than 0, return max subarray sum, otherwise, return the maximum value between max subarray sum and total sum minus min subarray sum.

Let's illustrate with an example: Input: [3,-1,2,-1] Output: 4

• totalSum will be '3'
• currMaxSum will after the first number will be '3', so maxSum also becomes '3'
• currMinSum will be '3' and as minSum was initialized as INT_MAX, minSum also becomes '3'
• Move to the next number '-1', now totalSum = '2', currMaxSum becomes '2' (3+-1), so maxSum stays at '3'
• currMinSum is '-1', hence minSum also becomes '-1'.
• Move to '2', now totalSum = '4', currMaxSum = '2', so maxSum stays at '3'. And currMinSum = '1', so minSum stays at '-1'
• Move to the last number '-1', totalSum = '3', currMaxSum = '2' so maxSum = '3'. currMinSum='-1' and as minSum = '-1', it stays at '-1'
• Now, as maxSum>0, return maximum of maxSum and totalSum - minSum which is max(3,3--1) = max(3,4) = 4 which is our output.

Solution:

Python:

1
2python
3class Solution(object):
4    def maxSubarraySumCircular(self, A):
5        # Initialize values
6        total, maxSum, curMax, minSum, curMin = 0, -float('inf'), 0, float('inf'), 0
7        for a in A: # For element a in A
8            # Calculate the running totals
9            curMax = max(curMax + a, a)
10            curMin = min(curMin + a, a)
11            maxSum = max(maxSum, curMax)
12            minSum = min(minSum, curMin)
13            total += a
14        # Based on the condition, return the maxSum or the total-minSum
15        return maxSum if maxSum < 0 else max(maxSum, total - minSum)

Java:

1
2java
3class Solution {
4    public int maxSubarraySumCircular(int[] A) {
5        int maxSum = Integer.MIN_VALUE;
6        int minSum = Integer.MAX_VALUE;
7        int total = 0;
8        int curMax = 0;
9        int curMin = 0;
10        for (int n : A){
11            // Calculating running totals
12            curMax = Math.max(curMax + n, n);
13            curMin = Math.min(curMin + n, n);
14            maxSum = Math.max(maxSum, curMax);
15            minSum = Math.min(minSum, curMin);
16            total += n;
17        }
18        // Based on the condition, return the maxSum or total-minSum
19        return maxSum < 0 ? maxSum : Math.max(maxSum, total - minSum);
20    }
21}

Javascript:

1
2javascript
3var maxSubarraySumCircular = function(A) {
4    let maxSum = -Number.MAX_VALUE;
5    let minSum = Number.MAX_VALUE;
6    let total = 0;
7    let curMax = 0;
8    let curMin = 0;
9    for (let n of A){
10        // Calculating running totals
11        curMax = Math.max(curMax + n, n);
12        curMin = Math.min(curMin + n, n);
13        maxSum = Math.max(maxSum, curMax);
14        minSum = Math.min(minSum, curMin);
15        total += n;
16    }
17    // Based on the condition, return maxSum or total-minSum
18    return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
19};

C++:

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

C#:

1
2csharp
3public class Solution {
4    public int MaxSubarraySumCircular(int[] A) {
5        int curMin = 0, curMax = 0;
6        int minSum = Int32.MaxValue, maxSum = Int32.MinValue, total = 0;
7        foreach(int a in A){
8            // Calculating running totals
9            curMax = Math.Max(a, curMax+a);
10            curMin = Math.Min(a, curMin+a);
11            maxSum = Math.Max(maxSum, curMax);
12            minSum = Math.Min(minSum, curMin);
13            total += a;
14        }
15        // Based on the condition, return maxSum or total-minSum
16        return maxSum > 0 ? Math.Max(maxSum, total - minSum) : maxSum;
17    }
18}

This algorithm works by traversing the array once and calculating the total sum, max sum subarray, and min sum subarray. The final comparison is based on a condition that if max sum of a subarray is less than 0, we return the max sum subarray. Otherwise, a comparison is made between max sum subarray and total sum minus min sum subarray. The maximum of these values is chosen as the maximum circular subarray sum since it would yield the highest possible subarray sum considering the input as a circular array.

Implementing such a solution requires a good understanding of the Kadane's algorithm and how max and min subarray sums are accumulated and can relate to circular array max sums. In summary, the solution adequately handles the maximum subarray sum calculation for circular arrays with time complexity of O(n) and space complexity of O(1), where n refers to the length of the input array. This is because the algorithm only requires a single pass through the array and does not require creating addition data structures.