552. Maximum Sum Circular Subarray
You are given a circular integer array nums: after the last element, the array wraps back around to the first. Find the largest possible sum of a non-empty subarray.
A subarray here is a run of consecutive elements on the circle, so it may either sit entirely inside the array or wrap across the end back to the front — but it can use each position at most once (its length never exceeds nums.length).
Return that maximum sum. Note the subarray must be non-empty: if every number is negative, the answer is the single largest element, not 0.
Example 1:
Input: nums = [1, -2, 3, -2]
Output: 3
Explanation: The best run is just [3]. No wrapping combination beats it: wrapping would have to include -2 on at least one side.
Example 2:
Input: nums = [5, -3, 5]
Output: 10
Explanation: Wrapping pays off: take the last 5 and the first 5 (a run on the circle), skipping the -3 in the middle, for 5 + 5 = 10.
Example 3:
Input: nums = [-3, -2, -3]
Output: -2
Explanation: Everything is negative, so the best non-empty subarray is the single element -2.
Constraints:
- 1 ≤ nums.length ≤ 3 * 10⁴
- -3 * 10⁴ ≤ nums[i] ≤ 3 * 10⁴
Hints:
Every subarray on a circle has one of two shapes: an ordinary middle run (no wrap), or a wrapping run — which is exactly the whole array with an ordinary middle run removed.
The best no-wrap sum is classic Kadane. For the best wrap sum, maximize total − (middle run) by finding the MINIMUM subarray sum with the same algorithm flipped.
One trap: if all elements are negative, the minimum subarray is the entire array, and total − min would be the empty subarray (sum 0), which is not allowed. Detect that case and fall back to plain Kadane.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, -2, 3, -2]
Expected output: 3