Code Implementation

class Solution:
    def maxSubarraySumCircular(self, nums):
        total = 0
        max_sum = cur_max = nums[0]
        min_sum = cur_min = nums[0]
        for n in nums:
            cur_max = max(n, cur_max + n)
            max_sum = max(max_sum, cur_max)
            cur_min = min(n, cur_min + n)
            min_sum = min(min_sum, cur_min)
            total += n
        if max_sum < 0:
            return max_sum
        return max(max_sum, total - min_sum)
      

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int total = 0, maxSum = nums[0], curMax = nums[0];
        int minSum = nums[0], curMin = nums[0];
        for (int n : nums) {
            curMax = max(n, curMax + n);
            maxSum = max(maxSum, curMax);
            curMin = min(n, curMin + n);
            minSum = min(minSum, curMin);
            total += n;
        }
        if (maxSum < 0) return maxSum;
        return max(maxSum, total - minSum);
    }
};
      

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int total = 0, maxSum = nums[0], curMax = nums[0];
        int minSum = nums[0], curMin = nums[0];
        for (int n : nums) {
            curMax = Math.max(n, curMax + n);
            maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(n, curMin + n);
            minSum = Math.min(minSum, curMin);
            total += n;
        }
        if (maxSum < 0) return maxSum;
        return Math.max(maxSum, total - minSum);
    }
}
      

var maxSubarraySumCircular = function(nums) {
    let total = 0, maxSum = nums[0], curMax = nums[0];
    let minSum = nums[0], curMin = nums[0];
    for (let n of nums) {
        curMax = Math.max(n, curMax + n);
        maxSum = Math.max(maxSum, curMax);
        curMin = Math.min(n, curMin + n);
        minSum = Math.min(minSum, curMin);
        total += n;
    }
    if (maxSum < 0) return maxSum;
    return Math.max(maxSum, total - minSum);
};
      

Problem Description

Given a circular integer array nums (meaning the end of the array connects back to the start), find the maximum possible sum of a non-empty subarray of nums. The subarray may wrap around the end of the array, but you cannot reuse elements (i.e., you can't select the same index twice).

Constraints include:

• Each element in nums is an integer (can be negative or positive).
• You must select at least one element.
• The resulting subarray must be contiguous in the circular sense.

Return the maximum possible sum of such a subarray.

Thought Process

At first glance, this problem looks similar to the classic "Maximum Subarray Sum" (Kadane's Algorithm). However, the twist is that the subarray can wrap around the end to the beginning, making it a circular array.

A brute-force approach would be to consider every possible subarray, including those that wrap around, and calculate their sums. However, this is inefficient for large arrays.

The challenge is to account for the circular nature efficiently, without explicitly checking every possibility. We need to find a way to use an optimized algorithm (like Kadane's) while still considering wrap-around subarrays.

Solution Approach

The solution uses a clever observation: the maximum circular subarray sum is either:

• The maximum subarray sum using standard Kadane's algorithm (no wrap), or
• The total sum of the array minus the minimum subarray sum (which is equivalent to taking all the elements except the minimum subarray, i.e., wrapping around that minimum).

1. Find the maximum subarray sum (no wrap):
   • Use Kadane's algorithm to find the largest contiguous subarray sum in the normal (non-circular) way.
2. Find the minimum subarray sum:
   • Use a similar process (Kadane's, but for minimum) to find the smallest contiguous subarray sum.
3. Compute the total sum of the array.
4. Check corner case:
   • If all numbers are negative, the "wrap-around" trick (total - min_subarray_sum) would give zero, which is not allowed. In this case, just return the maximum element (which is the non-wrap Kadane's result).
5. Return the maximum of the "non-wrap" and "wrap-around" cases:
   • That is, max(max_kadane, total - min_kadane).

This approach ensures we cover both possible cases for the maximum subarray sum in a circular array, all in linear time.

Example Walkthrough

Let's take the example: nums = [1, -2, 3, -2]

1. Max subarray sum (no wrap):
   • Using Kadane's algorithm: [3] gives sum 3.
2. Min subarray sum:
   • Using modified Kadane's: [-2] gives sum -2 (or [-2, 3, -2] gives -1, but -2 is smaller).
3. Total sum:
   • 1 + (-2) + 3 + (-2) = 0
4. Wrap-around sum:
   • Total - min_sum = 0 - (-2) = 2
5. Final answer:
   • max(3, 2) = 3

Thus, the maximum circular subarray sum is 3.

Time and Space Complexity

• Brute-force approach:
  • Would require checking every possible subarray, including wrap-arounds, resulting in O(n²) or worse time complexity.
• Optimized approach (Kadane's):
  • We make one pass to compute the max subarray sum, one pass for the min subarray sum, and one pass for the total sum, all combined into a single loop. This results in O(n) time complexity.
  • Space complexity is O(1), since we only use a few variables for tracking sums.

Summary

The key insight is to realize that the maximum circular subarray sum is either the standard maximum subarray (no wrap) or the total array sum minus the minimum subarray (wraps around the minimum). By leveraging Kadane's algorithm twice (once for max, once for min), we efficiently solve the problem in linear time and constant space. This approach elegantly handles both normal and circular cases with minimal code and maximum clarity.