Find maximum subarray sum in a circular array.
Input: nums=[1,-2,3,-2] → Output: 3
Input: nums=[5,-3,5] → Output: 10
Answer is max of (max subarray, total - min subarray). Handle all-negative case separately.
- Use Kadane for max subarray
- Use Kadane for min subarray (negate)
- If all negative return max subarray
- Otherwise return max(maxSub, total - minSub)
public int maxSubarraySumCircular(int[] nums) {
int total = 0, maxSum = nums[0], curMax = 0;
int minSum = nums[0], curMin = 0;
for (int num : nums) {
curMax = Math.max(num, curMax + num);
maxSum = Math.max(maxSum, curMax);
curMin = Math.min(num, curMin + num);
minSum = Math.min(minSum, curMin);
total += num;
}
return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
}
- Time Complexity: O(n)
- Space Complexity: O(1)