Maximum Sum Circular Subarray

Share

Find maximum subarray sum in a circular array.

Example 1
Input: nums=[1,-2,3,-2] → Output: 3
Example 2
Input: nums=[5,-3,5] → Output: 10

Solution Approach

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)
Java
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)