Maximum Sum Circular Subarray

Problem Overview

Given a circular array (the end connects back to the start), find the maximum possible sum of a non-empty contiguous subarray, where the subarray may wrap around the end.

Why solve this?

A direct extension of Kadane's algorithm: solving it requires running Kadane's twice — once normally, once inverted — and reasoning carefully about the one edge case where that trick breaks.

Pattern Recognition

Whenever an array is described as circular or wrapping, and the problem is otherwise a standard array-aggregate question, consider whether the wrapped case can be reframed as total sum minus the worst non-wrapped case, instead of literally simulating a circular traversal.

Prerequisites

• Maximum Subarray — this problem runs Kadane's algorithm twice: once as-is, once to find the minimum subarray.

Hints

1. A subarray that wraps around the end is equivalent to the elements NOT included in some ordinary (non-wrapping) subarray in the middle.
2. So the best wrapping subarray's sum equals totalSum minus the smallest possible non-wrapping subarray's sum.
3. Compute both the normal maximum subarray and the minimum subarray with the same running-aggregate idea, then take the better of the two candidates — but watch out for the case where every element is negative.

Approach

There are two cases for where the best subarray sits: entirely within the array (no wrap), or wrapping around the end. The non-wrapping case is exactly the standard Kadane's-algorithm maximum subarray. The wrapping case is equivalent to excluding some contiguous middle section from the full array — so its sum equals totalSum minus the minimum (most negative) subarray sum, which Kadane's algorithm can also compute by tracking a running minimum instead of a running maximum. The answer is the larger of these two candidates — except when every element is negative: in that case the 'best' wrapping subarray would exclude the entire array, leaving nothing, which isn't a valid non-empty subarray. That edge case is detected whenever the ordinary maximum subarray sum is itself negative (meaning every element is negative) — in which case the answer is just that ordinary, non-wrapping maximum subarray sum.

Code

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int totalSum = 0;
        int currentMax = 0, maxSum = nums[0];
        int currentMin = 0, minSum = nums[0];

        for (int num : nums) {
            currentMax = Math.max(currentMax + num, num);
            maxSum = Math.max(maxSum, currentMax);

            currentMin = Math.min(currentMin + num, num);
            minSum = Math.min(minSum, currentMin);

            totalSum += num;
        }

        if (maxSum < 0) {
            return maxSum;
        }
        return Math.max(maxSum, totalSum - minSum);
    }
}

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy