Maximum Sum Circular Subarray

When working with arrays, one of the most common problems we come across is finding the subarray with the maximum possible sum. However, what if the array is *circular*? That’s where things get a little more interesting.

A circular array is essentially an array that wraps around. For example, in a circular array, the element after the last one is the first one again. So, when you’re asked to find the maximum sum subarray in a circular array, you have to consider subarrays that may wrap from the end back to the beginning.

Input: nums = [1,-2,3,-2]
Output: 3
Explanation: The subarray [3] gives the maximum sum.

Using Kadane’s Algorithm to Solve It

Kadane’s Algorithm is a famous algorithm to solve the maximum subarray problem in linear time. It’s efficient and widely used. But for a circular array, we need to do a little extra.

The Code (Java)

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        int current_max = nums[0], maxSum = nums[0];
        int current_min = nums[0], minSum = nums[0];

        // Kadane's Algorithm for both max and min
        for (int i = 1; i < nums.length; i++) {
            current_max = Math.max(current_max + nums[i], nums[i]);
            maxSum = Math.max(maxSum, current_max);

            current_min = Math.min(current_min + nums[i], nums[i]);
            minSum = Math.min(minSum, current_min);
        }

        if (minSum == sum) {
            return maxSum;
        }

        return Math.max(maxSum, sum - minSum);
    }
}

Let’s Break It Down

This solution uses a clever technique: it computes two things using variations of Kadane's Algorithm—maximum subarray sum and minimum subarray sum. Then, it uses these to determine the answer.

What’s Really Happening Here?

• sum: It’s the total of all the elements in the array.
• current_max: Tracks the running maximum sum of the subarray ending at the current index.
• maxSum: Keeps the global maximum subarray sum (non-circular case).
• current_min: Tracks the running minimum sum of the subarray ending at the current index.
• minSum: Keeps the global minimum subarray sum.

Two Possibilities

1. Case 1: Normal Maximum Subarray (Non-Circular)
   We use Kadane’s algorithm to find the regular maximum subarray sum.
2. Case 2: Circular Maximum Subarray
   Here’s the trick: if you subtract the minimum subarray sum from the total sum, you effectively get the maximum circular subarray sum.

Why? Because removing the minimum subarray is like wrapping around the rest. If the total sum is 10 and the smallest chunk in the middle is −3, then the rest (which wraps around) gives 10 − (−3) = 13.

Step-by-Step Explanation

1. If there’s only one element, just return it. Simple edge case.

2. Compute the total sum of the array.

3. Use Kadane’s algorithm once to compute maxSum.

4. Use a variation to compute minSum.

5. If the minSum == sum, it means all elements are negative. In that case, return maxSum.

6. Otherwise, return the max of maxSum and sum - minSum.

Visual Example

Let’s look at nums = [5, -3, 5]

• maxSum (normal case) = 7 (from [5, -3, 5])
• sum = 7
• minSum = -3
• sum - minSum = 10

Answer: 10, which comes from the circular subarray [5, ..., 5] skipping -3.

Edge Case: All Negative Numbers

Consider: nums = [-3, -2, -3]

• sum = -8
• maxSum = -2
• minSum = -8

Here, the entire array is negative, so sum == minSum, and we return maxSum = -2.

Time and Space Complexity

• Time Complexity: O(n)
  We traverse the array once—very efficient!
• Space Complexity: O(1)
  We use constant space.

Real-Life Analogy

Imagine you're running a track that loops around like a circle. You want to run the segment of the track that gives you the most positive experience—say, the best scenery or the easiest terrain. You can start and end anywhere, and even wrap around the loop. That’s what this problem is asking you to do—just with numbers instead of scenery.

Conclusion

The "Maximum Sum Circular Subarray" problem may seem complex due to the circular nature, but with the help of Kadane’s algorithm and a clever twist, it becomes an elegant and efficient solution.

You learn how to handle circular scenarios by using the total sum and subtracting the minimum subarray. And importantly, you learn that edge cases like “all negative numbers” need to be handled gracefully.

It’s a great example of how sometimes solving a problem requires looking at it from two angles—and choosing the better one.

Happy Coding!