Problem #918: Maximum Sum Circular Subarray

Intuition & Strategy Breakdown

Calculate total sum, max subarray sum (Kadane), and min subarray sum. Max circular sum is max(max_sum, total - min_sum) unless max_sum < 0.

Python Solution

def maxSubarraySumCircular(nums):
    max_total, min_total = nums[0], nums[0]
    current_max, current_min = 0, 0
    total_sum = 0
    
    for x in nums:
        current_max = max(x, current_max + x)
        max_total = max(max_total, current_max)
        current_min = min(x, current_min + x)
        min_total = min(min_total, current_min)
        total_sum += x
        
    return max(max_total, total_sum - min_total) if max_total > 0 else max_total

Java Solution

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int maxTotal = nums[0], minTotal = nums[0];
        int currentMax = 0, currentMin = 0;
        int totalSum = 0;
        
        for (int x : nums) {
            currentMax = Math.max(x, currentMax + x);
            maxTotal = Math.max(maxTotal, currentMax);
            currentMin = Math.min(x, currentMin + x);
            minTotal = Math.min(minTotal, currentMin);
            totalSum += x;
        }
        
        return maxTotal > 0 ? Math.max(maxTotal, totalSum - minTotal) : maxTotal;
    }
}