Skip to main content
Talentd

Maximum Sum Circular Subarray - Solution & Explanation

MediumArrayDivide and ConquerDynamic ProgrammingQueue21 min readAsked at: Amazon, Microsoft, Apple +9
Practice this problem

Problem Statement

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.length
  • 1 <= 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.

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.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

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, initially 0;
  • The maximum prefix sum pmx, initially -infty;
  • The prefix sum s, initially 0;
  • The minimum subarray sum smi, initially infty;
  • 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 sum s minus the minimum prefix sum pmi can 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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)
Space Complexity: O(1)

Maintain Prefix Maximum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Kadane's Algorithm + Minimum Subarray TrickO(n)O(1)Best general solution. Minimal memory and simplest logic for circular maximum subarray.
Prefix Sum with Monotonic QueueO(n)O(n)Useful when modeling circular arrays with window constraints or extending to advanced sliding window problems.

Video Solution

Maximum Sum Circular Subarray | Leetcode #918 • Techdose • 104,275 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Sum Circular Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays