The problem
Find the maximum possible subarray sum in a circular array, where subarrays may wrap around the end.
Stuck? Reveal hints one at a time
How to approach it
- 1One pass computing simultaneously: Kadane max, Kadane min, and the total sum.
- 2Candidate A = maxKadane. Candidate B = total − minKadane.
- 3If maxKadane < 0 (all negatives), return maxKadane — candidate B would be an illegal empty subarray.
- 4Otherwise return max(A, B).
Key insight
A wrapping subarray is the complement of a non-wrapping one — so the wrap case reduces to MINIMIZING a subarray, which Kadane also does with flipped comparisons.
The solution
Watch out for
- The all-negative array: total − minSum = 0 describes an empty subarray, which is not allowed.
- Doubling the array and running a windowed Kadane is O(n²)-prone and unnecessary.