Maximum Sum Circular Subarray is an extension of the classic maximum subarray problem. You are given an integer array that is considered circular, meaning the end of the array wraps around to the beginning.
Your task is to find the maximum possible sum of a non-empty subarray, where the subarray may either:
- lie entirely within the array, or
- wrap around from the end back to the start
This circular behavior is what makes the problem interesting. In a normal array, subarrays are contiguous segments. In a circular array, the best subarray might include elements at the end and the beginning, skipping a middle section.
Why the circular aspect changes everything
If the array were not circular, the problem would be solved using Kadane’s algorithm, which finds the maximum subarray sum in linear time.
But in a circular array, the maximum sum subarray can look very different. For example, if the array is:
[5, -3, 5]
The best subarray is not [5, -3, 5] in the middle sense. Instead, it wraps around and picks the two 5s, giving a sum of 10.
So you need to consider two separate cases:
- The maximum subarray does not wrap
- The maximum subarray does wrap
The final answer is the better of these two.
Want to explore more coding problem solutions? Check out the Different Ways to Add Parentheses and Partition List coding problem solutions.
Case one: the non-circular maximum
This part is straightforward.
You apply the standard maximum subarray logic to find the best subarray that stays entirely within the array. This already gives you a valid candidate answer.
If all numbers are negative, this case alone gives the correct result, because wrapping would force you to include more negative numbers.
Case two: the circular maximum
The circular case is where the insight comes in.
A circular subarray that wraps around the array is equivalent to taking the entire array and excluding one contiguous subarray in the middle.
So instead of directly searching for a wrapping subarray, you ask a different question:
“What is the minimum sum subarray in the array?”
If you subtract that minimum sum subarray from the total sum of the array, what remains is the maximum wrapping subarray.
In other words:
total_sum − minimum_subarray_sum = maximum_circular_sum
This works because removing the worst contiguous segment leaves behind the best possible wraparound segment.
Why this logic is sound
In a circular array, any wraparound subarray can be represented as:
- Elements from the start of the array
- Plus elements from the end of the array
The part you skip is a single contiguous block in the middle.
Finding the minimum subarray gives you exactly the block you want to exclude.
This transforms the circular problem into two linear problems:
- Maximum subarray sum
- Minimum subarray sum
Both can be solved in one pass.
An important edge case to handle
If all elements in the array are negative, the “circular” formula breaks down.
Why?
Because the minimum subarray would be the entire array, and subtracting it would give zero, which is not allowed. The subarray must be non-empty.
In this case, the correct answer is simply the largest (least negative) element, which the non-circular maximum already gives you.
That’s why you must check for this condition and rely on the non-circular result when it occurs.
Performance in simple terms
The algorithm runs in linear time.
You scan the array once to compute:
- Total sum
- Maximum subarray sum
- Minimum subarray sum
Space usage is constant.
This is optimal and exactly what interviewers expect.
Top comments (0)