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:

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

The key question is: how do we efficiently handle the wrapping case without literally doubling the array and checking every possibility?

Key Constraints:

1 <= n <= 3 * 10^4 means our solution needs to be O(n) or O(n log n). An O(n^2) approach would handle 3 10^4 elements (about 9 10^8 operations), which is borderline and likely too slow.
-3 * 10^4 <= nums[i] <= 3 * 10^4 means values can be negative, positive, or zero. We need to handle the all-negatives case carefully.

Approach 1: Brute Force

Intuition

The most straightforward idea: just try every possible subarray, including the ones that wrap around, and track the maximum sum.

For each starting index i, we extend the subarray element by element (using modular arithmetic to wrap around), keeping a running sum and updating our answer. We stop after including at most n elements, since each element can appear at most once.

Algorithm

Initialize maxSum to negative infinity.
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).

Return maxSum.

Example Walkthrough

1Start: i=0, try all subarrays starting at index 0

i=0

-3

1/5

Code

Complexity Analysis

Time Complexity: O(n^2). We have two nested loops, each running up to n times. For each of the n starting positions, we extend the subarray up to n elements.
Space Complexity: O(1). We only use a few integer variables regardless of input size.

For every starting index, we recompute the sum from scratch by extending one element at a time. That is n full scans of the array. Can we break the circular problem into pieces that standard Kadane's can solve in a single pass?

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

Intuition

Here is the key insight that makes this problem elegant. 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 exactly 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. Now think about what is left out. The excluded elements form a contiguous subarray in the middle of the array. If the wrapping subarray has the maximum sum, then the excluded middle part must have the minimum sum. So:

maxWrappingSum = totalSum - minSubarraySum

The answer is simply max(maxSubarraySum, totalSum - minSubarraySum).

But there is one edge case: if all elements are negative, minSubarraySum equals totalSum (the entire array is the minimum subarray). That would give us totalSum - totalSum = 0, which corresponds to an empty subarray, and the problem requires a non-empty subarray. In this case, we just return maxSubarraySum (the least negative element).

Why Does This Work?

The magic of this approach comes from a simple observation about complementary subarrays. In a circular array, any wrapping subarray and the elements it skips are complementary: together they cover the entire array. So if we want to maximize the wrapping sum, we need to minimize the sum of the skipped elements. That is exactly what Kadane's algorithm for minimum subarray gives us.

By running Kadane's twice in one pass (once for max, once for min), we cover both cases in O(n) time. The only subtlety is the all-negatives edge case, where the "minimum subarray" is the entire array, and subtracting it would give an empty subarray sum of 0. Since the problem requires a non-empty subarray, we fall back to the standard maximum subarray answer in that case.

Algorithm

Initialize maxSum = nums[0], minSum = nums[0], currentMax = 0, currentMin = 0, and totalSum = 0.
For each element in the array:

currentMax = max(currentMax + nums[i], nums[i]) (Kadane's for max).
Update maxSum = max(maxSum, currentMax).
currentMin = min(currentMin + nums[i], nums[i]) (Kadane's for min).
Update minSum = min(minSum, currentMin).
Add nums[i] to totalSum.

If maxSum < 0, return maxSum (all elements are negative).
Otherwise, return max(maxSum, totalSum - minSum).

Example Walkthrough

1Initialize: currentMax=0, maxSum=5, currentMin=0, minSum=5, totalSum=0

-3

1/6

Code

Complexity Analysis

Time Complexity: O(n). We make a single pass through the array, doing O(1) work per element (two Kadane's updates and a running total).
Space Complexity: O(1). We only use a fixed number of integer variables.

Maximum Sum Circular Subarray

Understanding the Problem

Key Constraints:

Approach 1: Brute Force

Intuition

Algorithm

Example Walkthrough

Code

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

Intuition

Algorithm

Example Walkthrough

Code

Get Premium