Log inSign up
mediumLeetCodeNot Started

Maximum Sum Circular Subarray

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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 · Standard Non-wrapping Subarray:

Input: nums = [1, -2, 3, -2]
Output: 3
Explanation: Subarray [3] has maximum sum 3.

Example 2 · Wrapping Circular Subarray:

Input: nums = [5, -3, 5]
Output: 10
Explanation: Subarray [5, 5] (wrapping from index 2 to index 0) has maximum sum 5 + 5 = 10.

Example 3 · All Negative Numbers:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Kadane's Algorithm for Maximum Subarray
  • Circular array wrapping properties
  • Total sum complement logic

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the complement reduction: CircularMax = totalSum - MinSubarray.
  • Formulate Dual Kadane in a single loop.
  • Handle the all-negative edge case where totalSum == minKadane.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • Compute maxKadane and minKadane simultaneously in a single pass.
  • If maxKadane < 0 (all numbers are negative), return maxKadane directly.
  • Otherwise, return max(maxKadane, totalSum - minKadane).

Connected Patterns:

Maximum Subarray (Kadane's)Maximum Product SubarrayHouse Robber II (Circular DP)

1. Circular Scan for All Starting Positions (Brute Force)

Intuition

In a circular array, a subarray can start at any index i (0 <= i < n) and extend circularly for length len (1 <= len <= n). We can simulate this with two nested loops: for each start index i, we add elements at (i + j) % n and update the maximum running sum.

When to apply: Use to understand the circular wraparound geometry before applying Kadane's algorithm.

Brute Force — enumerate circular ranges

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Every non-empty circular range is a candidate
Visual state
Values and pointers at this exact step
array
S
5
-3
5
0
1
2
Variables at this step
start
0
length
1
sum
5
best
5
Check / comparison
Start at index 0 with length 1.
Decision / next transition
Record sum 5.
Why this step matters

Every non-empty circular range is a candidate.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int maxSubarraySumCircular(int[] nums) {
4 int n = nums.length;
5 int maxSum = nums[0];
6 for (int i = 0; i < n; i++) {
7 int sum = 0;
8 for (int len = 1; len <= n; len++) {
9 sum += nums[(i + len - 1) % n];
10 maxSum = Math.max(maxSum, sum);
11 }
12 }
13 return maxSum;
14 }
15 }
16
17 public static void main(String[] args) {
18 Solution sol = new Solution();
19 int[] nums = {1, -2, 3, -2};
20 System.out.println("Max Circular Subarray Sum: " + sol.maxSubarraySumCircular(nums));
21 }
22}

Time & Space Complexity

  • Time complexity: O(n^2) — Evaluating all n start positions for up to n steps takes O(n2) operations.
  • Space complexity: O(1) — Only constant extra variables are used.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Prefix Max and Suffix Sums (Better)

Intuition

Any subarray is either: Case 1: purely linear (computed via standard Kadane's). Case 2: circular, consisting of a non-empty prefix nums[0..i] and a non-empty suffix nums[j..n-1] with j > i + 1. We precompute rightMax[j] = max suffix sum from j to n-1. Then in a single pass we accumulate prefix sums and add rightMax[i+2].

When to apply: Use to understand the split nature of wrap-around subarrays without inverting Kadane's logic.

Better — prefix sums on a doubled array

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Every circular range can be represented as a normal range in the doubled array
Visual state
Values and pointers at this exact step
array
S
5
-3
5
0
1
2
Variables at this step
doubled
[5,-3,5,5,-3,5]
Check / comparison
Duplicate the array conceptually.
Decision / next transition
View it as [5,-3,5,5,-3,5].
Why this step matters

Every circular range can be represented as a normal range in the doubled array.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int maxSubarraySumCircular(int[] nums) {
4 int n = nums.length;
5 int cur = nums[0], maxLinear = nums[0];
6 for (int i = 1; i < n; i++) {
7 cur = Math.max(nums[i], cur + nums[i]);
8 maxLinear = Math.max(maxLinear, cur);
9 }
10 int[] rightMax = new int[n];
11 rightMax[n - 1] = nums[n - 1];
12 int suffix = nums[n - 1];
13 for (int i = n - 2; i >= 0; i--) {
14 suffix += nums[i];
15 rightMax[i] = Math.max(rightMax[i + 1], suffix);
16 }
17 int prefix = 0, maxCircular = Integer.MIN_VALUE;
18 for (int i = 0; i < n - 2; i++) {
19 prefix += nums[i];
20 maxCircular = Math.max(maxCircular, prefix + rightMax[i + 2]);
21 }
22 return Math.max(maxLinear, maxCircular);
23 }
24 }
25
26 public static void main(String[] args) {
27 Solution sol = new Solution();
28 int[] nums = {1, -2, 3, -2};
29 System.out.println("Max Circular Subarray Sum: " + sol.maxSubarraySumCircular(nums));
30 }
31}

Time & Space Complexity

  • Time complexity: O(n) — Precomputing rightMax takes O(n) and the prefix scan takes O(n).
  • Space complexity: O(n) — O(n) auxiliary space for the rightMax array.

3. Dual Kadane (Max & Min Subarray) (Optimal)

Intuition

1. A circular subarray that wraps around is equivalent to the entire array MINUS an internal non-circular subarray. To maximize the circular sum, we minimize that internal subarray sum: maxCircular = totalSum - minSubarraySum. 2. Edge case: If all numbers are negative, totalSum == minSubarraySum, leaving an empty subarray (which is invalid since subarrays must be non-empty). In this case, maxLinear < 0, and we simply return maxLinear.

When to apply: Use as the optimal O(n) time, O(1) space industry-standard solution.

Optimal — Kadane maximum and minimum

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Track both the best ordinary range and the smallest range that could be excluded
Visual state
Values and pointers at this exact step
array
S
5
-3
5
0
1
2
Variables at this step
total
5
maxEnding
5
maxSum
5
minEnding
5
minSum
5
Check / comparison
Initialize total, max-ending, max-sum, min-ending, and min-sum from 5.
Decision / next transition
All five values start at 5.
Why this step matters

Track both the best ordinary range and the smallest range that could be excluded.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int maxSubarraySumCircular(int[] nums) {
4 int totalSum = 0;
5 int curMax = 0, maxSum = nums[0];
6 int curMin = 0, minSum = nums[0];
7 for (int x : nums) {
8 curMax = Math.max(x, curMax + x);
9 maxSum = Math.max(maxSum, curMax);
10 curMin = Math.min(x, curMin + x);
11 minSum = Math.min(minSum, curMin);
12 totalSum += x;
13 }
14 return maxSum < 0 ? maxSum : Math.max(maxSum, totalSum - minSum);
15 }
16 }
17
18 public static void main(String[] args) {
19 Solution sol = new Solution();
20 int[] nums = {1, -2, 3, -2};
21 System.out.println("Max Circular Subarray Sum: " + sol.maxSubarraySumCircular(nums));
22 }
23}

Time & Space Complexity

  • Time complexity: O(n) — A single linear pass computing max and min Kadane state takes O(n) total operations.
  • Space complexity: O(1) — Only constant O(1) accumulator and tracker variables are maintained.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute ForceO(N^2)O(1)Run Kadane starting from each of the N possible circular start indices.Re-scanning array N times.
2.Better — Prefix + Suffix Max ArrayO(N)O(N)Compute max prefix sums and max suffix sums, combining them for wrapping cases.Auxiliary array allocation.
3.Optimal — Dual Kadane (Max & Min Subarray)OptimalO(N)O(1)Single pass computing totalSum, maxKadane, and minKadane in O(1) space.None; industry-standard optimal solution.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • All elements negative: nums = [-3, -2, -3] -> totalSum = -8, minKadane = -8. totalSum - minKadane = 0 (empty subarray), but non-empty subarray is required! Guard maxKadane < 0 returns -2.
  • Single element array: nums = [3] -> returns 3.
  • Array with all positive numbers: totalSum == maxKadane -> returns totalSum.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Maximum Sum Circular Subarray?

2.Why is the brute force approach suboptimal for large inputs in Maximum Sum Circular Subarray?

3.Which data structure or technique enables the optimal solution for Maximum Sum Circular Subarray?

Back to DSA Sheet