Maximum Sum Circular Subarray
Medium Kadane max & min
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
The array is circular (the end wraps to the start). Return the largest possible sum of a non-empty subarray that uses each element at most once.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: best subarray when the array wraps around.
Why this works: either the best piece doesn't wrap (normal Kadane), or it wraps, which means it's the total minus the worst middle piece.
Example: [5, -3, 5]
no wrap (Kadane): 5, 2, 7 → best 7wrap: total 7 - min piece (-3) = 10 → [5, 5]answer 10
✦Hints open one at a time
↗Approach
Run Kadane for the max subarray and for the min subarray at the same time. Answer = max(maxSum, total − minSum), except when maxSum < 0 (all negative) return maxSum.
</>Solution (Java)
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int total = 0, curMax = 0, curMin = 0;
int maxSum = Integer.MIN_VALUE, minSum = Integer.MAX_VALUE;
for (int x : nums) {
curMax = Math.max(x, curMax + x);
maxSum = Math.max(maxSum, curMax);
curMin = Math.min(x, curMin + x);
minSum = Math.min(minSum, curMin);
total += x;
}
if (maxSum < 0) return maxSum; // all numbers negative
return Math.max(maxSum, total - minSum); // no wrap vs wrap
}
}!Common mistake
Forgetting the all-negative case, which returns 0 (an empty subarray) instead of the largest element.
- Time: O(n).
- Space: O(1).