Maximum Sum Circular Subarray
The drill: Numbers sit in a circle — a run may wrap past the last index back to the front. Pick a nonempty contiguous run of that circular arrangement with the largest possible sum.
Numbers are arranged in a circle this time — after the last index, the sequence loops right back to the first. A contiguous run in this circular layout may wrap around that seam, continuing past the end into the front.
The task is finding the largest possible sum from one non-empty contiguous run of the circle — whether that run wraps around the seam or stays entirely within the normal left-to-right order.
A run may span at most the full circle once; it never doubles back over the same element twice. Only the best achievable sum matters as the answer.
- the array always holds at least one element
- values can be negative, zero, or positive, in any mix
- the chosen run must be non-empty and may wrap past the last index
- a run never revisits the same element twice, even when it wraps
HINT 1 THE NUDGE
A wraparound run is really two pieces glued at the seam: a suffix plus a prefix. If the wraparound run is the best one, what does the piece you're NOT taking — the middle you skip over — look like?
HINT 2 THE STRUCTURE
The skipped middle is just an ordinary, non-wrapping contiguous run. So a circular run's sum equals the total sum minus some ordinary run's sum — and you want that ordinary run to be as negative as possible.
HINT 3 ONE STEP FROM THE ANSWER
Run Kadane's rule twice: once for the largest ordinary run, once for the smallest. The circular answer is max(largest, total − smallest) — unless every number is negative, in which case skip the subtraction and just report the largest single run, since 'total − smallest' would otherwise leave nothing picked.
Circle [5, -3, 5], total 7. Both a max-Kadane and a min-Kadane start at the first value, 5.
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
total = sum(nums)
curMax = maxSum = nums[0]
curMin = minSum = nums[0]
for num in nums[1:]:
curMax = max(num, curMax + num)
maxSum = max(maxSum, curMax)
curMin = min(num, curMin + num)
minSum = min(minSum, curMin)
if maxSum < 0:
return maxSum
return max(maxSum, total - minSum)class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
n = len(nums)
best = nums[0]
for start in range(n):
running = 0
for length in range(1, n + 1):
idx = (start + length - 1) % n
running += nums[idx]
best = max(best, running)
return bestclass Solution {
public int maxSubarraySumCircular(int[] nums) {
int total = 0;
for (int num : nums) {
total += num;
}
int curMax = nums[0], maxSum = nums[0];
int curMin = nums[0], minSum = nums[0];
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
curMax = Math.max(num, curMax + num);
maxSum = Math.max(maxSum, curMax);
curMin = Math.min(num, curMin + num);
minSum = Math.min(minSum, curMin);
}
if (maxSum < 0) {
return maxSum;
}
return Math.max(maxSum, total - minSum);
}
}class Solution {
public int maxSubarraySumCircular(int[] nums) {
int n = nums.length;
int best = nums[0];
for (int start = 0; start < n; start++) {
int running = 0;
for (int length = 1; length <= n; length++) {
int idx = (start + length - 1) % n;
running += nums[idx];
best = Math.max(best, running);
}
}
return best;
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED