AlgoMaster Logo

Maximum Sum Circular Subarray

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

At first glance, this looks like the classic Maximum Subarray problem (Kadane's algorithm), but with a twist: the array is circular. That means a valid subarray can wrap around from the end of the array back to the beginning. For example, in [5, -3, 5], the subarray [5, 5] wraps around, taking the last element and the first element, for a sum of 10.

So we need to consider two types of subarrays:

  1. Normal subarrays that sit somewhere in the middle of the array (no wrapping).
  2. Wrapping subarrays that include some suffix of the array and some prefix of the array.

The challenge is handling the wrapping case efficiently, without doubling the array and checking every possibility.

Key Constraints:

  • 1 <= n <= 3 * 10^4 rules out a clean O(n^2) solution. At n = 3 10^4, that is around 9 10^8 operations, too slow for typical limits. The target is O(n).
  • -3 * 10^4 <= nums[i] <= 3 * 10^4 means values can be negative, positive, or zero, so the all-negatives case needs separate handling. The sum of the full array stays within int range (at most 3 10^4 3 10^4 = 9 10^8), so no overflow concerns.

Approach 1: Brute Force

Intuition

Try every possible subarray, including the ones that wrap around, and track the maximum sum.

For each starting index i, extend the subarray element by element using modular arithmetic to wrap around, keeping a running sum and updating the answer. Stop after including at most n elements, since each element can appear at most once. Modular indexing (i + j) % n means a subarray that starts near the end automatically continues from index 0, so wrapping subarrays are covered without building a second copy of the array.

Algorithm

  1. Initialize maxSum to negative infinity.
  2. For each starting index i from 0 to n-1:
    • Initialize currentSum = 0.
    • For each length j from 0 to n-1:
      • Add nums[(i + j) % n] to currentSum.
      • Update maxSum = max(maxSum, currentSum).
  3. Return maxSum.

Example Walkthrough

1Start: i=0, try all subarrays starting at index 0
0
i=0
5
1
-3
2
5
1/5

Code

This recomputes the sum from scratch for every starting index, which amounts to n full scans. The next approach splits the circular problem into two cases that standard Kadane's algorithm solves in a single pass.

Approach 2: Kadane's with Min Subarray (Optimal)

Intuition

Any subarray of a circular array falls into one of two cases:

Case 1: The maximum subarray does not wrap around. It sits entirely within the linear array. This is the classic maximum subarray problem, solved by Kadane's algorithm.

Case 2: The maximum subarray wraps around. It takes some elements from the end of the array and some from the beginning. The excluded elements then form a contiguous subarray in the middle. Since the wrapping subarray and the excluded middle together cover the whole array, their sums add up to totalSum. To make the wrapping sum as large as possible, the excluded middle must be as small as possible:

maxWrappingSum = totalSum - minSubarraySum

So the answer is max(maxSubarraySum, totalSum - minSubarraySum), where maxSubarraySum and minSubarraySum both come from Kadane's algorithm run on the same array.

One edge case remains. If all elements are negative, the minimum subarray is the entire array, so minSubarraySum equals totalSum. Then totalSum - minSubarraySum is 0, which corresponds to an empty subarray, and the problem requires a non-empty one. When maxSubarraySum < 0 (the signal that every element is negative), return maxSubarraySum, the least negative element.

Algorithm

  1. Initialize maxSum = nums[0], minSum = nums[0], currentMax = 0, currentMin = 0, and totalSum = 0.
  2. For each element in the array:
    1. currentMax = max(currentMax + nums[i], nums[i]) (Kadane's for max).
    2. Update maxSum = max(maxSum, currentMax).
    3. currentMin = min(currentMin + nums[i], nums[i]) (Kadane's for min).
    4. Update minSum = min(minSum, currentMin).
    5. Add nums[i] to totalSum.
  3. If maxSum < 0, return maxSum (all elements are negative).
  4. Otherwise, return max(maxSum, totalSum - minSum).

Example Walkthrough

1Initialize: currentMax=0, maxSum=5, currentMin=0, minSum=5, totalSum=0
0
5
1
-3
2
5
1/6

Code