Maximum Sum Circular Subarray
Problem
Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C. Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.) Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)
Either the best subarray is contiguous (standard Kadane gives maxSum) or it wraps. The wrapping case is the complement of the smallest contiguous subarray, so its sum is total − minSum. Return max(maxSum, total − minSum). Edge case: if every element is negative, total − minSum is 0 (empty complement) — fall back to maxSum.
nums = [5, -3, 5]10def max_sum_circular_subarray(nums):
total = 0
cur_max = best_max = nums[0]
cur_min = best_min = nums[0]
total += 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: return best_max
return max(best_max, total - best_min)function maxSumCircularSubarray(nums) {
let total = nums[0];
let curMax = nums[0], bestMax = nums[0];
let curMin = nums[0], bestMin = nums[0];
for (let i = 1; i < nums.length; i++) {
const x = nums[i];
curMax = Math.max(x, curMax + x); bestMax = Math.max(bestMax, curMax);
curMin = Math.min(x, curMin + x); bestMin = Math.min(bestMin, curMin);
total += x;
}
if (bestMax < 0) return bestMax;
return Math.max(bestMax, total - bestMin);
}public int maxSumCircularSubarray(int[] nums) {
int total = nums[0];
int curMax = nums[0], bestMax = nums[0];
int curMin = nums[0], bestMin = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
curMax = Math.max(x, curMax + x); bestMax = Math.max(bestMax, curMax);
curMin = Math.min(x, curMin + x); bestMin = Math.min(bestMin, curMin);
total += x;
}
if (bestMax < 0) return bestMax;
return Math.max(bestMax, total - bestMin);
}int maxSumCircularSubarray(vector<int>& nums) {
int total = nums[0];
int curMax = nums[0], bestMax = nums[0];
int curMin = nums[0], bestMin = nums[0];
for (int i = 1; i < (int)nums.size(); i++) {
int x = nums[i];
curMax = max(x, curMax + x); bestMax = max(bestMax, curMax);
curMin = min(x, curMin + x); bestMin = min(bestMin, curMin);
total += x;
}
if (bestMax < 0) return bestMax;
return max(bestMax, total - bestMin);
}Explanation
Because the array is circular, the best subarray either sits in the middle like normal, or it wraps around the ends. We cleverly handle both with one pass and no actual wrapping.
For the normal case we run standard Kadane to get best_max, the largest contiguous sum. For the wrapping case, notice that a wrap-around subarray is exactly the leftover after you remove some middle chunk. To make the wrap biggest, remove the smallest middle chunk — so the wrap sum is total - best_min, where best_min comes from running Kadane to find the minimum sum.
The answer is max(best_max, total - best_min). There's one trap: if every number is negative, best_min equals the whole array and total - best_min becomes 0 (an empty subarray, which isn't allowed). The check if best_max < 0 catches this and returns best_max.
Example: [5, -3, 5]. Total is 7, the smallest middle chunk is -3, so the wrap is 7 - (-3) = 10. The non-wrap best is 7.
The bigger one, 10, is the answer — the wrap takes the two 5s by going around the -3.