Maximum Sum Circular Subarray
MedPrompt
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 * 104
Approaches
2 approaches with complexity analysis and trade-offs.
This approach exhaustively checks every possible contiguous subarray in the circular array. It iterates through all possible starting points and, for each starting point, considers all possible lengths from 1 up to the total number of elements n. By calculating the sum for each of these subarrays and keeping track of the maximum sum found, it guarantees finding the correct answer.
Algorithm
- Initialize
max_global_sumwith a very small number (or the first element). - Use a nested loop structure. The outer loop
ifrom0ton-1selects the starting element of the subarray. - The inner loop
jfrom0ton-1determines the length of the subarray (from 1 to n). - Inside the inner loop, calculate the sum of the current subarray. To handle wrapping, use the modulo operator:
index = (i + j) % n. - Keep a
current_sumfor the subarray starting atiand extending forj+1elements. - After calculating the sum of each possible subarray, compare it with
max_global_sumand update if it's larger. - After all loops complete,
max_global_sumwill hold the result.
Walkthrough
The brute-force method systematically explores all potential subarrays. A subarray in a circular context is defined by its starting position and its length. We can implement this with two nested loops.
- The outer loop iterates through each element of the array,
nums[i], treating it as the starting point of a potential maximum subarray. - The inner loop then extends the subarray from this starting point, one element at a time. It calculates the sum of the current subarray and updates the overall maximum sum found so far.
- The circular nature of the array is handled by using the modulo operator (
%) to calculate the indices of elements, which allows the subarray to 'wrap around' from the end of the array to the beginning.
class Solution { public int maxSubarraySumCircular(int[] nums) { int n = nums.length; int maxGlobalSum = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { int currentSum = 0; for (int j = 0; j < n; j++) { int index = (i + j) % n; currentSum += nums[index]; if (currentSum > maxGlobalSum) { maxGlobalSum = currentSum; } } } return maxGlobalSum; }}Complexity
Time
O(n^2), where n is the length of the input array. The two nested loops result in a quadratic number of operations as we check every start position against every possible length.
Space
O(1), as we only use a constant amount of extra space for variables like `maxGlobalSum` and `currentSum`.
Trade-offs
Pros
Simple to understand and implement.
It is a straightforward translation of the problem definition into code.
Cons
Highly inefficient for larger arrays due to its quadratic time complexity.
Likely to result in a 'Time Limit Exceeded' error on competitive programming platforms for typical constraints.
This optimal approach solves the problem in linear time by recognizing that the maximum sum subarray is either a standard one or one that wraps around. It uses Kadane's algorithm to find the maximum sum of a non-wrapping subarray. For the wrapping case, it calculates the total sum of the array and subtracts the minimum sum of a non-wrapping subarray (also found using a variant of Kadane's). The final answer is the larger of these two possibilities, with a special check for the edge case where all numbers are negative.
Algorithm
- The maximum sum can be in one of two forms:
- A standard (non-wrapping) subarray.
- A wrapping subarray (prefix + suffix).
- Case 1: Find the maximum subarray sum for a non-wrapping array. This is a classic problem solved by Kadane's Algorithm. Let's call this
max_sum. - Case 2: The sum of a wrapping subarray is
total_array_sum - sum_of_the_middle_part. To maximize this value, we need to find the subarray with the minimum sum and subtract it from the total. The minimum subarray sum can also be found using a variation of Kadane's algorithm. Let's call thismin_sum. - The maximum possible wrapping sum is
total_sum - min_sum. - Combine Cases: The answer is
max(max_sum, total_sum - min_sum). - Edge Case: If all numbers are negative,
max_sumwill be the largest (least negative) number.min_sumwill be equal tototal_sum. In this situation,total_sum - min_sumwould be 0, representing an empty subarray, which is not allowed. So, ifmax_sumis negative, the answer is simplymax_sum. This can be checked byif (max_sum > 0). If not, the wrapping case is invalid, and we returnmax_sum.
Walkthrough
This efficient method is based on a clever observation. The subarray with the maximum sum can either be a contiguous block in the 'unrolled' array or a block that wraps around the ends.
-
Non-Wrapping Subarray: We can find the maximum sum of any non-wrapping subarray using Kadane's algorithm. We iterate through the array, keeping track of the maximum sum ending at the current position and the overall maximum sum found so far.
-
Wrapping Subarray: A subarray that wraps around is equivalent to the entire array minus a subarray from the middle. To maximize the sum of the wrapping part (
total_sum - middle_sum), we must find themiddle_sumthat is as small as possible. Therefore, we need to find the minimum subarray sum. This can also be done in linear time with a simple modification to Kadane's algorithm (usingmininstead ofmax).
The potential maximum sum from a wrapping subarray is total_sum - min_subarray_sum.
Finally, we compare the results from both cases. However, we must handle the edge case where all elements are negative. In this scenario, the minimum subarray is the entire array, making total_sum - min_subarray_sum = 0. This represents an empty subarray, which is invalid. If the standard maximum subarray sum is negative, it means all numbers are non-positive, and this must be our answer.
class Solution { public int maxSubarraySumCircular(int[] nums) { int totalSum = 0; int maxSum = nums[0]; int currentMax = 0; int minSum = nums[0]; int currentMin = 0; for (int num : nums) { // Standard Kadane's for maximum subarray sum currentMax = Math.max(currentMax + num, num); maxSum = Math.max(maxSum, currentMax); // Kadane's variant for minimum subarray sum currentMin = Math.min(currentMin + num, num); minSum = Math.min(minSum, currentMin); totalSum += num; } // If maxSum is positive, the answer is the max of non-wrapping sum (maxSum) // and wrapping sum (totalSum - minSum). // If maxSum is negative, it means all numbers are negative or zero. // In this case, totalSum - minSum would be 0 (as minSum == totalSum), // which corresponds to an empty subarray. So, we must return maxSum. if (maxSum > 0) { return Math.max(maxSum, totalSum - minSum); } else { return maxSum; } }}Complexity
Time
O(n), where n is the number of elements in the array. The algorithm makes a single pass to compute all necessary values (total sum, max subarray sum, and min subarray sum).
Space
O(1), as it only requires a few variables to keep track of sums, regardless of the input array's size.
Trade-offs
Pros
Extremely efficient with O(n) time complexity.
Solves the problem in a single pass through the array.
Elegantly combines two cases (wrapping and non-wrapping) for a complete solution.
Cons
The logic can be slightly non-intuitive at first, particularly the idea of inverting the problem to find the minimum subarray sum.
The edge case where all numbers are negative needs careful handling to avoid returning an incorrect result (0 for an empty subarray).
Solutions
Solution
class Solution {public int maxSubarraySumCircular(int[] nums) { int s1 = nums[0], s2 = nums[0], f1 = nums[0], f2 = nums[0], total = nums[0]; for (int i = 1; i < nums.length; ++i) { total += nums[i]; f1 = nums[i] + Math.max(f1, 0); f2 = nums[i] + Math.min(f2, 0); s1 = Math.max(s1, f1); s2 = Math.min(s2, f2); } return s1 > 0 ? Math.max(s1, total - s2) : s1; }}class Solution {public: int maxSubarraySumCircular(vector<int> &nums) { int s1 = nums[0], s2 = nums[0], f1 = nums[0], f2 = nums[0], total = nums[0]; for (int i = 1; i < nums.size(); ++i) { total += nums[i]; f1 = nums[i] + max(f1, 0); f2 = nums[i] + min(f2, 0); s1 = max(s1, f1); s2 = min(s2, f2); } return s1 > 0 ? max(s1, total - s2) : s1; }};class Solution: def maxSubarraySumCircular(self, nums: List[int]) -> int: s1 = s2 = f1 = f2 = nums[0] for num in nums[1:]: f1 = num + max(f1, 0) f2 = num + min(f2, 0) s1 = max(s1, f1) s2 = min(s2, f2) return s1 if s1 <= 0 else max(s1, sum(nums) - s2)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.