Watch 10 video solutions for Maximum Sum Circular Subarray, a medium level problem involving Array, Divide and Conquer, Dynamic Programming. This walkthrough by Techdose has 102,125 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 to the beginning of the array. 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 only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.
Example 1:
Input: nums = [1,-2,3,-2] Output: 3 Explanation: Subarray [3] has maximum sum 3.
Example 2:
Input: nums = [5,-3,5] Output: 10 Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.
Example 3:
Input: nums = [-3,-2,-3] Output: -2 Explanation: Subarray [-2] has maximum sum -2.
Constraints:
n == nums.length1 <= n <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104Problem Overview: You are given an integer array where the end of the array connects back to the beginning, forming a circular structure. The task is to compute the maximum possible sum of a non-empty subarray, where the subarray may wrap from the end of the array to the start.
The circular constraint creates two possible scenarios: the maximum subarray lies entirely within the array (normal case) or it wraps around the boundary. Efficient solutions detect both cases and return the larger sum.
Approach 1: Kadane's Algorithm with Minimum Subarray Trick (O(n) time, O(1) space)
The standard maximum subarray problem is solved using Kadane's algorithm. Iterate through the array while maintaining the best subarray ending at the current index and the global maximum. This handles the non-circular case directly.
For circular subarrays, observe that a wrapping subarray is equivalent to the total array sum minus the minimum subarray sum. If you remove the smallest contiguous segment, the remaining elements form the best circular segment. Run a modified Kadane pass to compute the minimum subarray sum. The final answer becomes max(maxSubarray, totalSum - minSubarray). A special case occurs when all numbers are negative; in that scenario, the regular Kadane result must be returned.
This method uses constant memory and scans the array once. It relies heavily on concepts from dynamic programming and is the most practical solution in interviews.
Approach 2: Prefix Sum with Monotonic Queue (Conceptual DP View) (O(n) time, O(n) space)
Another way to reason about the circular constraint is to duplicate the array conceptually and use prefix sums to evaluate subarray sums across boundaries. Maintain a running prefix sum and use a monotonic queue to keep track of candidate minimum prefixes within a valid window of size n. The difference between the current prefix and the smallest prefix in the queue gives the best subarray ending at the current index.
This technique is common in advanced sliding window problems and uses ideas from queue structures and monotonic queue optimization. It generalizes well to constrained subarray problems where the length is limited.
Recommended for interviews: The Kadane-based approach is what most interviewers expect. It demonstrates you understand both the classic maximum subarray problem and how to adapt it for circular arrays. Mentioning the prefix-sum + monotonic queue approach shows deeper algorithmic awareness, but implementing Kadane correctly is usually sufficient.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Kadane's Algorithm + Minimum Subarray Trick | O(n) | O(1) | Best general solution. Minimal memory and simplest logic for circular maximum subarray. |
| Prefix Sum with Monotonic Queue | O(n) | O(n) | Useful when modeling circular arrays with window constraints or extending to advanced sliding window problems. |