Maximum Sum Circular Subarray
Description
Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.
A circular array means the end of the array connects back to the beginning. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].
A subarray may include each element of the array at most once. In other words, if the subarray wraps around the circular boundary, it cannot reuse any element.
Your task is to find the contiguous subarray (which may wrap around) with the largest sum.
Examples
Example 1
Input: nums = [1, -2, 3, -2]
Output: 3
Explanation: The subarray [3] (just the single element at index 2) has the maximum sum of 3. Even though the array is circular, no wrap-around subarray produces a larger sum. For instance, wrapping from index 2 to index 0 gives [3, -2, 1] = 2, which is smaller.
Example 2
Input: nums = [5, -3, 5]
Output: 10
Explanation: The maximum sum comes from the circular subarray [5, 5], which wraps from the last element (index 2) to the first element (index 0), skipping the middle element -3. The sum is 5 + 5 = 10. The best non-wrapping subarray is [5, -3, 5] with sum 7, which is smaller.
Example 3
Input: nums = [-3, -2, -3]
Output: -2
Explanation: When all elements are negative, the best subarray is the single element with the largest value. Here, [-2] has sum -2. Wrapping around would only add more negative numbers, making the sum worse.
Constraints
- n == nums.length
- 1 ≤ n ≤ 3 × 10^4
- -3 × 10^4 ≤ nums[i] ≤ 3 × 10^4
Editorial
Brute Force
Intuition
The most direct way to solve this problem is to consider every possible subarray — including ones that wrap around the circular boundary — and find the one with the maximum sum.
Think of the circular array as a ring of numbers. A subarray is any consecutive stretch of numbers along this ring, and it can be at most n elements long (since each element can appear at most once).
We can enumerate all possible subarrays by fixing each starting index and extending the subarray one element at a time using modular arithmetic to handle the wrap-around. For starting index i, we try lengths 1, 2, ..., n, computing the sum by adding nums[(i + k) % n] for each extension.
For each starting position, we accumulate a running sum and update our global maximum whenever we find a larger sum. This guarantees we check every contiguous subarray in the circular array.
Step-by-Step Explanation
Let's trace through nums = [5, -3, 5]:
Step 1: Start at index 0. Try subarrays starting here.
- Length 1: [5] → sum = 5. Best so far = 5.
- Length 2: [5, -3] → sum = 5 + (-3) = 2. Best so far = 5.
- Length 3: [5, -3, 5] → sum = 2 + 5 = 7. Best so far = 7.
Step 2: Start at index 1. Try subarrays starting here.
- Length 1: [-3] → sum = -3. Best so far = 7.
- Length 2: [-3, 5] → sum = -3 + 5 = 2. Best so far = 7.
- Length 3: [-3, 5, 5] (wraps to index 0) → sum = 2 + 5 = 7. Best so far = 7.
Step 3: Start at index 2. Try subarrays starting here.
- Length 1: [5] → sum = 5. Best so far = 7.
- Length 2: [5, 5] (wraps to index 0) → sum = 5 + 5 = 10. Best so far = 10!
- Length 3: [5, 5, -3] (wraps through index 0, 1) → sum = 10 + (-3) = 7. Best so far = 10.
Step 4: All starting positions exhausted. Return 10.
Brute Force — Checking All Circular Subarrays — Watch how we try every starting index and extend subarrays using modular arithmetic, including ones that wrap around the array boundary.
Algorithm
- Initialize best_sum = -∞
- For each starting index i from 0 to n-1:
- Initialize current_sum = 0
- For each length len from 1 to n:
- Add nums[(i + len - 1) % n] to current_sum
- Update best_sum = max(best_sum, current_sum)
- Return best_sum
Code
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int n = nums.size();
int bestSum = INT_MIN;
for (int i = 0; i < n; i++) {
int currentSum = 0;
for (int len = 1; len <= n; len++) {
currentSum += nums[(i + len - 1) % n];
bestSum = max(bestSum, currentSum);
}
}
return bestSum;
}
};class Solution:
def maxSubarraySumCircular(self, nums: list[int]) -> int:
n = len(nums)
best_sum = float('-inf')
for i in range(n):
current_sum = 0
for length in range(1, n + 1):
current_sum += nums[(i + length - 1) % n]
best_sum = max(best_sum, current_sum)
return best_sumclass Solution {
public int maxSubarraySumCircular(int[] nums) {
int n = nums.length;
int bestSum = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int currentSum = 0;
for (int len = 1; len <= n; len++) {
currentSum += nums[(i + len - 1) % n];
bestSum = Math.max(bestSum, currentSum);
}
}
return bestSum;
}
}Complexity Analysis
Time Complexity: O(n²)
We have two nested loops. The outer loop iterates over n starting positions, and for each starting position the inner loop extends the subarray up to length n. This results in n × n = n² iterations total, each doing O(1) work.
Space Complexity: O(1)
We only use a few integer variables (bestSum, currentSum, loop counters). No additional data structures are needed.
Why This Approach Is Not Efficient
The brute force solution checks all n² possible subarrays. With n up to 3 × 10^4, that means up to 9 × 10^8 operations — far too slow for a typical time limit of 1-2 seconds.
The fundamental inefficiency is that we recompute overlapping sums from scratch for each starting position. We do not carry any information from one starting index to the next.
The key insight for improvement comes from a classic technique: Kadane's algorithm can find the maximum subarray sum in a single pass for a non-circular array. But what about the circular case where the subarray wraps around?
Here is the elegant observation: if the maximum-sum subarray wraps around the ends of the array, then the elements not in that subarray form a contiguous chunk in the middle. The sum of the wrapping subarray equals totalSum - middleChunkSum. To maximize the wrapping subarray sum, we need to minimize the middle chunk sum. So the circular case reduces to finding the minimum subarray sum — which is also solvable in O(n) using a modified Kadane's algorithm.
By running Kadane's for both the maximum and minimum subarray in a single pass, we solve the entire problem in O(n).
Optimal Approach - Kadane's Max and Min
Intuition
Imagine the circular array as a ring. The maximum-sum subarray falls into exactly one of two patterns:
Case 1 — No wrap-around: The best subarray sits entirely within the linear array, not crossing the boundary. This is the classic maximum subarray problem solved by Kadane's algorithm.
Case 2 — Wrap-around: The best subarray wraps from the end of the array back to the beginning. Picture the ring: the chosen elements form an arc that crosses the "seam" between the last and first elements.
Here is the key insight for Case 2: if the maximum subarray wraps around, then the elements that are not part of it form a contiguous block in the middle of the linear array. The wrap-around sum equals:
wrap_sum = totalSum - sum_of_middle_block
To maximize wrap_sum, we need to minimize the middle block — in other words, find the minimum contiguous subarray sum. This is a mirror of Kadane's algorithm: instead of tracking the running maximum, we track the running minimum.
The final answer is max(maxKadane, totalSum - minKadane).
There is one edge case: if all elements are negative, then minKadane equals totalSum (the entire array is the minimum subarray), making totalSum - minKadane = 0, which represents an empty subarray. Since the problem requires a non-empty subarray, we return maxKadane in this case (which will be the least-negative single element).
Step-by-Step Explanation
Let's trace through nums = [5, -3, 5]:
Step 1: Initialize variables.
- maxCurr = 0 (running max subarray ending here), maxSum = -∞ (global max)
- minCurr = 0 (running min subarray ending here), minSum = +∞ (global min)
- totalSum = 0
Step 2: Process nums[0] = 5.
- totalSum = 0 + 5 = 5
- maxCurr = max(0 + 5, 5) = 5. maxSum = max(-∞, 5) = 5.
- minCurr = min(0 + 5, 5) = 5. minSum = min(+∞, 5) = 5.
Step 3: Process nums[1] = -3.
- totalSum = 5 + (-3) = 2
- maxCurr = max(5 + (-3), -3) = max(2, -3) = 2. maxSum = max(5, 2) = 5.
- minCurr = min(5 + (-3), -3) = min(2, -3) = -3. minSum = min(5, -3) = -3.
Step 4: Process nums[2] = 5.
- totalSum = 2 + 5 = 7
- maxCurr = max(2 + 5, 5) = 7. maxSum = max(5, 7) = 7.
- minCurr = min(-3 + 5, 5) = min(2, 5) = 2. minSum = min(-3, 2) = -3.
Step 5: Compute final answer.
- Case 1 (no wrap): maxSum = 7
- Case 2 (wrap): totalSum - minSum = 7 - (-3) = 10
- Are all elements negative? maxSum = 7 > 0, so no.
- Answer = max(7, 10) = 10.
The wrap-around subarray [5, 5] gives sum 10 by excluding the minimum subarray [-3].
Kadane's Max + Min — Single-Pass Solution — Watch how we simultaneously track the maximum and minimum running subarrays in one pass, then combine them to handle both the non-wrapping and wrapping cases.
Algorithm
- Initialize: maxCurr = 0, maxSum = -∞, minCurr = 0, minSum = +∞, totalSum = 0
- For each element num in nums:
- totalSum += num
- maxCurr = max(maxCurr + num, num) (Kadane's max: extend or restart)
- maxSum = max(maxSum, maxCurr)
- minCurr = min(minCurr + num, num) (Kadane's min: extend or restart)
- minSum = min(minSum, minCurr)
- If maxSum < 0 (all elements negative): return maxSum
- Otherwise: return max(maxSum, totalSum - minSum)
Code
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int totalSum = 0;
int maxCurr = 0, maxSum = INT_MIN;
int minCurr = 0, minSum = INT_MAX;
for (int num : nums) {
totalSum += num;
// Kadane's for maximum subarray
maxCurr = max(maxCurr + num, num);
maxSum = max(maxSum, maxCurr);
// Kadane's for minimum subarray
minCurr = min(minCurr + num, num);
minSum = min(minSum, minCurr);
}
// If all elements are negative, maxSum is the answer
// (wrapping case would give empty subarray with sum 0)
if (maxSum < 0) return maxSum;
return max(maxSum, totalSum - minSum);
}
};class Solution:
def maxSubarraySumCircular(self, nums: list[int]) -> int:
total_sum = 0
max_curr, max_sum = 0, float('-inf')
min_curr, min_sum = 0, float('inf')
for num in nums:
total_sum += num
# Kadane's for maximum subarray
max_curr = max(max_curr + num, num)
max_sum = max(max_sum, max_curr)
# Kadane's for minimum subarray
min_curr = min(min_curr + num, num)
min_sum = min(min_sum, min_curr)
# If all elements negative, wrapping case gives 0 (empty)
# which is invalid, so return max_sum directly
if max_sum < 0:
return max_sum
return max(max_sum, total_sum - min_sum)class Solution {
public int maxSubarraySumCircular(int[] nums) {
int totalSum = 0;
int maxCurr = 0, maxSum = Integer.MIN_VALUE;
int minCurr = 0, minSum = Integer.MAX_VALUE;
for (int num : nums) {
totalSum += num;
// Kadane's for maximum subarray
maxCurr = Math.max(maxCurr + num, num);
maxSum = Math.max(maxSum, maxCurr);
// Kadane's for minimum subarray
minCurr = Math.min(minCurr + num, num);
minSum = Math.min(minSum, minCurr);
}
// If all negative, wrapping case is invalid (empty subarray)
if (maxSum < 0) return maxSum;
return Math.max(maxSum, totalSum - minSum);
}
}Complexity Analysis
Time Complexity: O(n)
We traverse the array exactly once. At each step, we perform a constant number of operations: one addition (totalSum), two max/min comparisons for Kadane's max, two max/min comparisons for Kadane's min, and one comparison to update global bests. Total: O(n).
Space Complexity: O(1)
We use only five integer variables (totalSum, maxCurr, maxSum, minCurr, minSum) regardless of input size. No additional data structures are needed.