Maximum Sum Circular Subarray

How it works

The maximum circular subarray sum falls into one of two cases: either the subarray does not wrap around, or it does. For the non-wrapping case, standard Kadane's algorithm finds the maximum subarray sum. For the wrapping case, if we remove a contiguous middle portion from the array, what remains is a prefix plus a suffix. Removing the minimum subarray sum leaves behind the maximum wrapping sum, which equals total - minSubarraySum. We take the better of these two cases, but if all elements are negative, the maximum is simply the largest single element.

Steps

1. Initialize globMax and globMin to nums[0], and set curMax, curMin, and total to 0.
2. For each num in nums:
   • Update curMax = max(curMax + num, num) and globMax = max(globMax, curMax).
   • Update curMin = min(curMin + num, num) and globMin = min(globMin, curMin).
   • Add num to total.
3. If globMax > 0, return max(globMax, total - globMin). Otherwise, return globMax.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Forgetting the All-Negative Edge Case

When all elements are negative, the minimum subarray equals the entire array, so total - minSum becomes zero. This would incorrectly suggest an empty subarray. The fix is to check if maxSum > 0 before considering the wrap-around case, or equivalently return maxSum when all elements are negative.

Confusing Wrap-Around Logic

A common mistake is trying to directly find the maximum wrap-around subarray. The key insight is that if a subarray wraps around, it means we are excluding a contiguous middle portion. Therefore, the wrap-around max equals total - minSubarraySum. Failing to realize this leads to overly complicated solutions.

Incorrect Kadane Initialization

Initializing curMax and curMin to nums[0] instead of 0 can cause off-by-one errors when updating the global max/min. The standard Kadane approach resets the running sum when it becomes detrimental, which requires careful initialization to avoid skipping or double-counting the first element.

from typing import List

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        globMax, globMin = nums[0], nums[0]
        curMax, curMin = 0, 0
        total = 0

        for num in nums:
            curMax = max(curMax + num, num)
            curMin = min(curMin + num, num)
            total += num
            globMax = max(globMax, curMax)
            globMin = min(globMin, curMin)

        return max(globMax, total - globMin) if globMax > 0 else globMax

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int globMax = nums[0], globMin = nums[0];
        int curMax = 0, curMin = 0, total = 0;

        for (int& num : nums) {
            curMax = max(curMax + num, num);
            curMin = min(curMin + num, num);
            total += num;
            globMax = max(globMax, curMax);
            globMin = min(globMin, curMin);
        }

        return globMax > 0 ? max(globMax, total - globMin) : globMax;
    }
};