Circular Subarray
The max subarray might wrap around the end. The trick: the wrapping case equals totalSum − minSubarray. So the answer is max(normalKadane, totalSum − minKadane). Handle the all-negative edge case.
How It Works
In a circular array the best subarray may wrap around the end and re-enter at the front. The elegant reduction: a wrapping subarray is exactly the complement of a non-wrapping one, so its sum equals totalSum minus some contiguous middle section. Maximizing the wrap therefore means minimizing that middle — totalSum − minSubarraySum.
Run Kadane's twice in one pass: once tracking the maximum subarray (the normal case) and once tracking the minimum (for the wrapping case), then answer max(maxKadane, totalSum − minKadane). One edge case matters: if every element is negative, the minimum subarray is the whole array and the complement is empty, so you must fall back to maxKadane alone. Total cost stays O(n) time, O(1) space.
Step-by-Step Visualization
Code
static int maxSubarraySumCircular(int[] nums) {
int totalSum = 0;
int maxSum = Integer.MIN_VALUE, curMax = 0;
int minSum = Integer.MAX_VALUE, 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);
totalSum += num;
}
return maxSum < 0 ? maxSum : Math.max(maxSum, totalSum - minSum);
}Tips & Gotchas
Practice Problems
- 1Maximum Sum Circular Subarray
- 2Maximum Subarray
- 3Rotate Array
About the Kadane's / Subarray Pattern
At each position, decide: should I extend the previous subarray, or start fresh here? Track the running sum and the global maximum. This elegant approach finds the maximum subarray sum in O(n).
When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.
Common Array Interview Problems
- Two Sum
- Best Time to Buy & Sell Stock
- Maximum Subarray
- Merge Intervals
- Product of Array Except Self
- Container With Most Water
Frequently Asked Questions
Why does totalSum minus the minimum subarray give the best wrapping sum?
A wrapping subarray covers a suffix plus a prefix, leaving out one contiguous middle block. Its sum is the total minus that block, so the wrap is maximized precisely when the excluded block's sum is minimized — which is what a min-Kadane pass computes.
What goes wrong in the all-negative case?
The minimum subarray becomes the entire array, making totalSum − minSum equal zero, which corresponds to an illegal empty subarray. Detect this — for example, when maxKadane is negative — and return maxKadane, the least-bad single element.
Could I instead double the array and run a windowed Kadane?
Concatenating the array to itself and limiting subarrays to length n works but requires a monotonic-deque-over-prefix-sums approach, costing more code and O(n) space. The two-Kadane complement trick achieves the same result in O(1) space with a few extra lines.