315. Maximum Sum Circular Subarray

The best circular subarray is either a normal (non-wrapping) subarray — found by standard Kadane — or a wrapping one, which equals the total sum minus the smallest non-wrapping subarray. Take the larger, with one guard for the all-negative case.

Idea

A circular subarray is one of two shapes:

1. Non-wrapping — an ordinary contiguous subarray. Standard Kadane finds its maximum.
2. Wrapping — it uses a prefix and a suffix, leaving a gap in the middle. Maximizing a wrapping sum is the same as minimizing the gap: wrap_max = total - min_subarray, where min_subarray is the smallest contiguous subarray (found by Kadane run for minimums).

The answer is max(max_subarray, total - min_subarray). One caveat: if all numbers are negative, the min subarray is the entire array, making total - min_subarray = 0 (an empty pick), which isn't allowed. Detect this with max_subarray < 0 and just return max_subarray.

Algorithm

In one pass track: cur_max/best_max (Kadane for max), cur_min/best_min (Kadane for min), and total.

• cur_max = max(cur_max + x, x), update best_max.
• cur_min = min(cur_min + x, x), update best_min.
• total += x.

Return best_max if best_max < 0, else max(best_max, total - best_min).

Worked example: [1,-2,3,-2]

• best_max (non-wrapping): the subarray [3] gives 3.
• total = 0; best_min = [-2] = -2; wrap = 0 - (-2) = 2... but the wrap [3,-2,1] (=,wrapping) gives 3-2+1... let's trust the formula: max(3, 0 - (-2)) = max(3, 2) = 3.

Answer: 3.

Complexity

• Time: O(n) — one pass, two Kadanes.
• Space: O(1).

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int total = 0;
        int curMax = 0, bestMax = nums[0];
        int curMin = 0, bestMin = nums[0];
        for (int x : nums) {
            curMax = Math.max(curMax + x, x);
            bestMax = Math.max(bestMax, curMax);
            curMin = Math.min(curMin + x, x);
            bestMin = Math.min(bestMin, curMin);
            total += x;
        }
        if (bestMax < 0) {
            return bestMax;
        }
        return Math.max(bestMax, total - bestMin);
    }
}