TL;DR
Run Kadane twice — max subarray and min subarray — and return max(maxSum, total - minSum), guarding the all-negative case — O(n) time, O(1) space.
Approach 1 — Brute force: every circular subarray
Try every start and every length up to n, using modular indexing to wrap.
from typing import List
def maxSubarraySumCircular(nums: List[int]) -> int:
n = len(nums)
best = nums[0]
for start in range(n):
total = 0
for length in range(1, n + 1):
total += nums[(start + length - 1) % n]
best = max(best, total)
return best
Complexity: O(n^2) time, O(1) space. At n = 3 * 10^4 the ~10^9 iterations are too slow.
Approach 2 — Two Kadanes: max case vs. wrap case
The insight — split by shape. Any candidate subarray either does not wrap or does wrap:
- Non-wrapping: the answer is exactly the ordinary maximum subarray — plain Kadane gives
maxSum.
- Wrapping: a wrapping subarray keeps a suffix and a prefix while excluding a contiguous middle block. Its sum is
total - (sum of the excluded middle). To make what we keep as large as possible, we exclude the middle block with the smallest sum. That smallest contiguous block is found by an inverted Kadane (minSum). So the best wrapping sum is total - minSum.
The greedy-choice property (why the same local rule solves both): Kadane’s greedy rule — drop the running accumulator whenever it stops helping — is optimal for the maximum subarray (drop a prefix once it goes negative) and, applied with the comparisons flipped, for the minimum subarray (drop a prefix once it goes positive). A negative prefix can only hurt a max run, and a positive prefix can only hurt a min run; in both directions the local “reset when the prefix works against you” decision never forfeits a better global answer. We reuse that one greedy idea twice and combine the two results.
The edge case: if every element is negative, maxSum is itself negative, and the wrap formula total - minSum equals total - total = 0, which corresponds to excluding everything — an empty subarray, not allowed. Detect this by maxSum < 0 and return maxSum (the least-negative single element).
from typing import List
def maxSubarraySumCircular(nums: List[int]) -> int:
total = nums[0]
cur_max = best_max = nums[0]
cur_min = best_min = nums[0]
for x in nums[1:]:
cur_max = max(x, cur_max + x)
best_max = max(best_max, cur_max)
cur_min = min(x, cur_min + x)
best_min = min(best_min, cur_min)
total += x
if best_max < 0: # all elements negative
return best_max
return max(best_max, total - best_min)
Walkthrough on nums = [5,-3,5]:
- Init:
total=5, cur_max=best_max=5, cur_min=best_min=5.
x=-3: cur_max=max(-3,5-3=2)=2, best_max=5; cur_min=min(-3,5-3=2)=-3, best_min=-3; total=2.x=5: cur_max=max(5,2+5=7)=7, best_max=7; cur_min=min(5,-3+5=2)=-3, best_min=-3; total=7.best_max=7 >= 0. Answer = max(7, total - best_min) = max(7, 7-(-3)=10) = 10.
The wrapping subarray [5, 5] (indices 2 and 0) beats the non-wrapping best of 7, and it is found as total - (min middle block [-3]).
Complexity: O(n) time (single pass computing both Kadanes and the total), O(1) space.
Common pitfalls
- Forgetting the all-negative guard. Without
if best_max < 0, an input like [-3,-2,-3] returns 0 (empty selection) instead of -2.
- Computing
total - best_min where best_min is allowed to be the whole array — that only becomes an issue precisely in the all-negative case, which the guard covers.
- Running the min-Kadane with
max comparisons by mistake; the minimum subarray needs min(x, cur_min + x).
- Trying to handle the wrap by physically doubling the array (
nums + nums) and running Kadane with a length cap — it works but is trickier to bound to length n than the total - minSum trick.
Pattern takeaway
For circular-array optimization, decompose into “doesn’t wrap” and “wraps,” and turn the wrapping case into its complement: keeping the best wrap = total minus the worst middle you exclude. Reuse the greedy Kadane rule in both directions, and always sanity-check the degenerate all-same-sign case.