Maximum Sum Circular Subarray solution and explanation
Google
Infosys
9 more videos on this problem
Maximum Sum Circular Subarray | Leetcode #918Techdose · 14:02 · 104K views
Maximum Sum Circular Subarray - Leetcode 918 - PythonNeetCodeIO · 16:49 · 79K views
Maximum Sum Circular Subarray | With Proof | Leetcode 918 | codestorywithMIKcodestorywithMIK · 30:55 · 30K views
Maximum Sum Circular Subarray | LeetCode 918Codebix · 16:34 · 18K views
LeetCode 918. Maximum Sum Circular Subarray Explanation and Solutionhappygirlzt · 9:41 · 6K views
Leetcode 918 Maximum Sum Circular Subarray ||CodingDecoded SDE sheetCoding Decoded · 13:29 · 5K views
Leetcode - Maximum Sum Circular Subarray (Python)Timothy H Chang · 14:58 · 2K views
Maximum Sum Circular Subarray | Leetcode - 918Algorithms Made Easy · 5:53 · 2K views
Maximum Sum Circular Subarray - Kadane’s Algorithm - Dynamic Programming - PythonCheatCode Ninja · 4:31 · 1K views
Daily Leetcode #1023: Jan 18, 2023 - 918. Maximum Sum Circular SubarrayProgramming Live with Larry · 20:50 · 690 views
The problem
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
Approach overview
Problem 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 1: Kadane's Algorithm for Max Sum and Modified for Min Sum
The main idea is to use Kadane's Algorithm to find the maximum subarray sum for two scenarios: one, where the subarray wraps around the end and beginning of the array, and two, where it does not.
Calculate the maximum subarray sum using Kadane's algorithm in the normal way. Then calculate the minimum subarray sum using a similar technique but by negating the result. The maximum possible circular subarray sum will be the maximum value between the normal subarray sum and the total array sum minus the minimum subarray sum.
def maxSubarraySumCircular(nums):
def kadane(gen):
current = result = nums[0]
for x in gen:
current = x + max(current, 0)
result = max(result, current)
return result
s = sum(nums)
max_normal = kadane(nums)
max_circular = s + kadane(-x for x in nums[1:])
if max_circular == 0:
return max_normal
return max(max_normal, max_circular)public class Solution {
public int maxSubarraySumCircular(int[] A) {
int sumAll = 0;
// Calculate total sum of the array
for (int a : A) {
sumAll += a;
}
// Standard Kadane's Algorithm for the maximum subarray sum
int currentMax = A[0], maxSoFar = A[0];
for (int i = 1; i < A.length; i++) {
currentMax = Math.max(A[i], currentMax + A[i]);
maxSoFar = Math.max(maxSoFar, currentMax);
}
// Modified Kadane's to find minimum so far
int currentMin = A[0], minSoFar = A[0];
for (int i = 1; i < A.length; i++) {
currentMin = Math.min(A[i], currentMin + A[i]);
minSoFar = Math.min(minSoFar, currentMin);
}
int max_circular = sumAll - minSoFar;
return max_circular == 0 ? maxSoFar : Math.max(maxSoFar, max_circular);
}
}#include <vector>
#include <algorithm>
#include <numeric>
int kadane(const std::vector<int>& A) {
int current_max = A[0], max_so_far = A[0];
for (int i = 1; i < A.size(); i++) {
current_max = std::max(A[i], current_max + A[i]);
max_so_far = std::max(max_so_far, current_max);
}
return max_so_far;
}
int maxSubarraySumCircular(std::vector<int>& A) {
int sumAll = std::accumulate(A.begin(), A.end(), 0);
int max_normal = kadane(A);
for (auto& num : A) num = -num;
int max_circular = sumAll + kadane(A);
return max_circular == 0 ? max_normal : std::max(max_normal, max_circular);
}function maxSubarraySumCircular(A) {
const kadane = (arr) => {
let current = arr[0];
let maxSum = arr[0];
for (let i = 1; i < arr.length; i++) {
current = Math.max(arr[i], current + arr[i]);
maxSum = Math.max(maxSum, current);
}
return maxSum;
};
const totalSum = A.reduce((a, b) => a + b, 0);
const maxNormal = kadane(A);
// Invert signs of array elements for min kadane
for (let i = 0; i < A.length; i++) A[i] = -A[i];
const maxCircular = totalSum + kadane(A);
return maxCircular === 0 ? maxNormal : Math.max(maxNormal, maxCircular);
}#include <stdio.h>
#include <limits.h>
int kadane(int *arr, int n) {
int current_max = arr[0], global_max = arr[0];
for (int i = 1; i < n; i++) {
current_max = (arr[i] > current_max + arr[i]) ? arr[i] : current_max + arr[i];
global_max = (global_max > current_max) ? global_max : current_max;
}
return global_max;
}
int maxSubarraySumCircular(int* nums, int numsSize) {
int sum = 0, max_kadane, min_kadane;
for (int i = 0; i < numsSize; i++) sum += nums[i];
max_kadane = kadane(nums, numsSize);
// Inverting the sign for min kadane operation
for (int i = 0; i < numsSize; i++) nums[i] = -nums[i];
min_kadane = kadane(nums, numsSize);
int max_circular = sum + min_kadane; // sum - (-min_kadane)
// If max_circular is 0, it means all elements are negative
return max_circular == 0 ? max_kadane : (max_kadane > max_circular ? max_kadane : max_circular);
}public class Solution {
public int MaxSubarraySumCircular(int[] A) {
int sumAll = 0;
foreach (int a in A) sumAll += a; // Total sum of array
int maxCurrent = A[0], maxGlobal = A[0];
for (int i = 1; i < A.Length; i++) {
maxCurrent = Math.Max(A[i], maxCurrent + A[i]);
maxGlobal = Math.Max(maxGlobal, maxCurrent);
}
int minCurrent = A[0], minGlobal = A[0];
for (int i = 1; i < A.Length; i++) {
minCurrent = Math.Min(A[i], minCurrent + A[i]);
minGlobal = Math.Min(minGlobal, minCurrent);
}
int maxCircular = sumAll - minGlobal;
return maxCircular == 0 ? maxGlobal : Math.Max(maxGlobal, maxCircular);
}
}The function kadane is a helper function designed to employ Kadane's algorithm for any iterable. It efficiently finds the maximum sum of a contiguous subarray.
We then calculate the total sum of the array and determine the maximum subarray sum using Kadane's. By reversing the signs of the array elements and applying Kadane's algorithm again, we effectively discover the minimum subarray sum. The maximum sum is then checked against two cases:
- Max subarray sum without wrapping.
- Max circular subarray sum calculated as total sum minus the minimum subarray sum.
Time Complexity: O(n) — as both the applications of Kadane's algorithm are linear.
Space Complexity: O(1) — no additional space is used except for a few variables.
Approach 2: Dynamic Programming Explanation
Instead of using basic Kadane's approach, we can consider computing the maximum subarray sum with additional memory for storing maximum and minimum values up to each index. This allows precise tracing of subarrays—as contiguous and potential wrap-around cases.
def maxSubarraySumCircular(nums):
total, max_sum, min_sum, cur_max, cur_min = 0, nums[0], nums[0], 0, 0
for num in nums:
cur_max = max(cur_max + num, num)
max_sum = max(max_sum, cur_max)
cur_min = min(cur_min + num, num)
min_sum = min(min_sum, cur_min)
total += num
return max_sum if max_sum < 0 else max(max_sum, total - min_sum)public class Solution {
public int maxSubarraySumCircular(int[] nums) {
int total = 0, max_sum = nums[0], min_sum = nums[0];
int cur_max = 0, cur_min = 0;
for (int num : nums) {
cur_max = Math.max(cur_max + num, num);
max_sum = Math.max(max_sum, cur_max);
cur_min = Math.min(cur_min + num, num);
min_sum = Math.min(min_sum, cur_min);
total += num;
}
return max_sum < 0 ? max_sum : Math.max(max_sum, total - min_sum);
}
}#include <vector>
#include <algorithm>
int maxSubarraySumCircular(std::vector<int>& nums) {
int total = 0, max_sum = nums[0], min_sum = nums[0];
int cur_max = 0, cur_min = 0;
for (int num : nums) {
cur_max = std::max(cur_max + num, num);
max_sum = std::max(max_sum, cur_max);
cur_min = std::min(cur_min + num, num);
min_sum = std::min(min_sum, cur_min);
total += num;
}
return (max_sum < 0) ? max_sum : std::max(max_sum, total - min_sum);
}function maxSubarraySumCircular(nums) {
let total = 0, max_sum = nums[0], min_sum = nums[0];
let cur_max = 0, cur_min = 0;
nums.forEach((num) => {
cur_max = Math.max(cur_max + num, num);
max_sum = Math.max(max_sum, cur_max);
cur_min = Math.min(cur_min + num, num);
min_sum = Math.min(min_sum, cur_min);
total += num;
});
return max_sum < 0 ? max_sum : Math.max(max_sum, total - min_sum);
}#include <stdio.h>
int maxSubarraySumCircular(int* nums, int numsSize) {
int total = 0, max_sum = nums[0], min_sum = nums[0];
int cur_max = 0, cur_min = 0;
for (int i = 0; i < numsSize; i++) {
cur_max = cur_max + nums[i] > nums[i] ? cur_max + nums[i] : nums[i];
max_sum = max_sum > cur_max ? max_sum : cur_max;
cur_min = cur_min + nums[i] < nums[i] ? cur_min + nums[i] : nums[i];
min_sum = min_sum < cur_min ? min_sum : cur_min;
total += nums[i];
}
return max_sum < 0 ? max_sum : (max_sum > total - min_sum ? max_sum : total - min_sum);
}public class Solution {
public int MaxSubarraySumCircular(int[] nums) {
int total = 0, max_sum = nums[0], min_sum = nums[0];
int cur_max = 0, cur_min = 0;
foreach (var num in nums) {
cur_max = Math.Max(cur_max + num, num);
max_sum = Math.Max(max_sum, cur_max);
cur_min = Math.Min(cur_min + num, num);
min_sum = Math.Min(min_sum, cur_min);
total += num;
}
return max_sum < 0 ? max_sum : Math.Max(max_sum, total - min_sum);
}
}In this dynamic programming approach, two critical values are maintained: the current maximum and minimum subarray sums found. We update each possibility as we iterate across elements and calculate the total array sum to assist in determining potential circular maximum subarrays later.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Maintain Prefix Maximum
The maximum sum of a circular subarray can be divided into two cases:
- Case 1: The subarray with the maximum sum does not include the circular part, which is the ordinary maximum subarray sum;
- Case 2: The subarray with the maximum sum includes the circular part, which can be transformed into: the total sum of the array minus the minimum subarray sum.
Therefore, we maintain the following variables:
- The minimum prefix sum
pmi, initially0; - The maximum prefix sum
pmx, initially-infty; - The prefix sum
s, initially0; - The minimum subarray sum
smi, initiallyinfty; - The answer
ans, initially-infty.
Next, we only need to traverse the array nums. For the current element x we are traversing, we perform the following update operations:
- Update the prefix sum
s = s + x; - Update the answer
ans = max(ans, s - pmi), which is the answer for Case 1 (the prefix sumsminus the minimum prefix sumpmican give the maximum subarray sum); - Update
smi = min(smi, s - pmx), which is the minimum subarray sum for Case 2; - Update
pmi = min(pmi, s), which is the minimum prefix sum; - Update
pmx = max(pmx, s), which is the maximum prefix sum.
After the traversal, we return the maximum value of ans and s - smi as the answer.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
function maxSubarraySumCircular(nums: number[]): number {
let [pmi, pmx] = [0, -Infinity];
let [ans, s, smi] = [-Infinity, 0, Infinity];
for (const x of nums) {
s += x;
ans = Math.max(ans, s - pmi);
smi = Math.min(smi, s - pmx);
pmi = Math.min(pmi, s);
pmx = Math.max(pmx, s);
}
return Math.max(ans, s - smi);
}func maxSubarraySumCircular(nums []int) int {
const inf = 1 << 30
pmi, pmx := 0, -inf
ans, s, smi := -inf, 0, inf
for _, x := range nums {
s += x
ans = max(ans, s-pmi)
smi = min(smi, s-pmx)
pmi = min(pmi, s)
pmx = max(pmx, s)
}
return max(ans, s-smi)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Kadane's Algorithm for Max Sum and Modified for Min Sum | Time Complexity: O(n) — as both the applications of Kadane's algorithm are linear. Space Complexity: O(1) — no additional space is used except for a few variables. |
| Dynamic Programming Explanation | Time Complexity: O(n) |
| Maintain Prefix Maximum | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Maximum Sum Circular Subarray easy or hard?
Maximum Sum Circular Subarray is rated Medium difficulty on LeetCode. The challenge is recognizing that a circular maximum subarray can be derived from totalSum minus the minimum subarray, which extends the classic Kadane's algorithm idea.
Maximum Sum Circular Subarray Python/Java solution
Most implementations use Kadane's algorithm. The code maintains current maximum and minimum subarray sums while iterating through the array and tracking the total sum. This approach works in Python, Java, C++, JavaScript, and other languages with identical O(n) time complexity.
How to solve Maximum Sum Circular Subarray in O(n)?
Run Kadane's algorithm to find the maximum subarray sum in the normal (non-circular) case. Compute the total sum of the array and run a modified Kadane pass to find the minimum subarray sum. The circular result is totalSum minus minSubarray. Return the maximum of the normal result and the circular result, handling the edge case where all values are negative.
What is the best approach for Maximum Sum Circular Subarray?
Kadane's algorithm combined with a minimum-subarray calculation is the most efficient approach. First compute the standard maximum subarray using Kadane's algorithm. Then compute the minimum subarray and subtract it from the total array sum to handle circular wrapping. The final result is the maximum of the two values, with O(n) time and O(1) space.
Is Maximum Sum Circular Subarray asked at Google/Amazon/Meta?
Maximum Sum Circular Subarray appears in interview preparation lists for companies like Amazon, Google, and Meta because it tests understanding of Kadane's algorithm and edge-case reasoning with circular arrays. Variants of this problem are commonly asked in coding interviews.
What data structure is used in Maximum Sum Circular Subarray?
The optimal solution mainly uses dynamic programming concepts with running variables, not complex data structures. Alternative formulations may use prefix sums and a monotonic queue to maintain candidate minimum prefixes when evaluating circular subarrays.
What is the time complexity of Maximum Sum Circular Subarray?
The optimal solution runs in O(n) time because the array is scanned once to compute the maximum subarray and once more for the minimum subarray. Space complexity is O(1) since only a few running variables are maintained during iteration.