Problem Statement

Maximum Sum Circular Subarray

You have an array of numbers, and it is circular, which means the end loops back around to the start. Picture the numbers written around the edge of a clock, so after the last number you are back at the first one. A subarray is a chunk of numbers that sit next to each other. Because the array is circular, that chunk is allowed to wrap from the end back into the beginning. Your job: pick a non-empty chunk whose numbers add up to the biggest total possible. Here is the key idea. The best chunk is one of two kinds. Either it sits in the middle without wrapping, or it wraps around the ends. A wrapping chunk is the same as the whole array minus a chunk in the middle, so to make the wrapping chunk as big as possible you remove the smallest middle chunk. So the answer is the larger of two things: the best normal chunk, or the total of everything minus the worst middle chunk. The one exception is when every number is negative, which we handle separately.

mediumArrayDynamic ProgrammingDynamic ProgrammingTime: O(n) · Space: O(1)

Signals to notice

max subarray sum in circular arraywrapping allowedtotal minus min subarray

Brute force first

Check all circular subarrays — O(n²).

The key insight

Max circular = max(Kadane's, totalSum - minSubarraySum). Wrapping case = total minus the minimum non-wrapping middle. O(n).

Trace it on `nums=[5,-3,5]`

init: maxSum=curMax=-inf, minSum=curMin=+inf, total=0
num=5: curMax=max(5,-inf)=5 -> maxSum=5; curMin=min(5,+inf)=5 -> minSum=5; total=5
num=-3: curMax=max(-3,5-3)=2 -> maxSum=5; curMin=min(-3,5-3)=-3 -> minSum=-3; total=2
num=5: curMax=max(5,2+5)=7 -> maxSum=7; curMin=min(5,-3+5)=2 -> minSum=-3; total=7
loop ends: maxSum=7 (not <0), so consider wrapping case
return max(maxSum, total-minSum) = max(7, 7-(-3)) = max(7,10) = 10

What must stay true

Wrapping subarray = total - non-wrapping middle. Minimize middle = maximize wrapping.

Shape of the loop

maxSum=curMax=-inf; minSum=curMin=+inf; total=0
for num in nums:
    curMax = max(num, curMax+num);  maxSum = max(maxSum, curMax)
    curMin = min(num, curMin+num);  minSum = min(minSum, curMin)
    total += num
return maxSum if maxSum < 0 else max(maxSum, total - minSum)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

All negative: minSubarray = total, giving circular = 0. Use normal Kadane's in this case.

Dynamic Programming Pattern