Loading…

mediumDynamic ProgrammingLC #918Sometimes asked

Maximum Sum Circular Subarray

Q: How do you solve Maximum Sum Circular Subarray using the Brute Force — Try Every Circular Subarray approach?

When to use it: Open with this to frame the search space, then flag it as too slow for n = 3·10⁴ before pivoting to Kadane. The most direct reading: a circular subarray is determined by where it starts and how long it is. So fix each start index `i`, then grow the subarray one element at a time — using `(i + k) % n` to wrap past the end — accumulating a running sum and recording the maximum. **Why this covers wrapping for free.** Modular indexing means a subarray starting near the end naturally continues into the front of the array. Capping the length at `n` enforces the 'each index at most once' rule. No special wrap logic is needed — the `% n` does it. **Why this is the honest baseline.** It makes 'every possible circular subarray' literally executable and is trivially correct, which is exactly what you want to state before optimizing. It also handles the non-empty requirement automatically since every candidate has length ≥ 1. **Why we don't ship it.** With `n` up to `3·10⁴`, `O(n²)` is ~900 million operations — too slow. And it's wasteful: as the start advances, the sums it computes overlap heavily with the previous start's work. That overlap, plus the classic Maximum Subarray connection, points straight at Kadane. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Maximum Sum Circular Subarray using the Standard Kadane — Non-Wrapping Only (Building Block) approach?

When to use it: Establish Kadane as the tool, then immediately show it misses the wrapping case (e.g. [5,-3,5]) — motivating the full solution. Kadane's algorithm is the linear core. Maintain a running subarray sum `curMax`; at each element decide whether to extend the current subarray or start fresh at the current element: `curMax = max(x, curMax + x)`. Track the largest `curMax` seen in `maxSum`. That value is the best *non-wrapping* subarray sum. **Why this is the right building block.** The circular problem is just Maximum Subarray with one extra case (the wrap). Establishing the linear answer first mirrors how you'd reason on a whiteboard and gives half the final answer directly — the non-wrapping candidate. **Where it falls short.** Consider `[5, -3, 5]`. Kadane finds `5 - 3 + 5 = 7` (the whole array) or just `5`. But the best circular subarray takes the last `5`, wraps around, and grabs the first `5` for `10`. Kadane alone cannot see this because it only considers contiguous runs in the *linear* array — it never wraps. **The fix this motivates.** A wrapping subarray is a suffix plus a prefix — i.e. the entire array *minus* a contiguous middle chunk. To maximize the wrap, minimize that excluded middle. So the full solution runs Kadane a second time to find the *minimum* subarray, and computes `total − minSum`. The next approach combines both into one pass. Time complexity: O(n). Space complexity: O(1).

LCPractice

Dynamic Programming · 16 of 44 · 10 min

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: formally, the next element of nums[i] is nums[(i + 1) % 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.

In plain English

Find the largest sum of a contiguous run of elements, where 'contiguous' may wrap from the end of the array back to the front. No element is used twice. The wrap is the only difference from classic Maximum Subarray (Kadane).

Examples

Example 1

Input: nums = [1,-2,3,-2]
Output: 3
Note: The non-wrapping subarray [3] gives 3 — wrapping doesn't help here.

Example 2

Input: nums = [5,-3,5]
Output: 10
Note: The wrapping subarray [5, (wrap), 5] sums to 10, beating the best non-wrapping run (5-3+5 = 7).

Example 3

Input: nums = [-3,-2,-3]
Output: -2
Note: All negative — the answer is the largest single element, -2. The total-minus-min trick must NOT return 0.

Constraints

n == nums.length
1 ≤ n ≤ 3 × 10⁴
-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴
The subarray must be non-empty and use each buffer index at most once

Clarifying questions4First question: Can the subarray wrap around the end?Explore questions

Q1.Can the subarray wrap around the end?
Yes — that's the whole point. A run like nums[n-1], nums[0], nums[1] is valid. Without wrapping this is plain Maximum Subarray.
Q2.Must the subarray be non-empty?
Yes. This matters enormously: when every element is negative the answer is the largest (least negative) single element, not 0.
Q3.Can an element be used more than once?
No. Even though it's circular, each buffer index appears at most once, so a wrapping subarray can't be longer than n.
Q4.Are all elements possibly negative?
Yes, and that's the key edge case. The total-minus-min trick must be guarded, or it returns 0 (the empty subarray) instead of the max element.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The best circular subarray is either non-wrapping (plain Kadane maximum) or wrapping. A wrapping subarray equals the total sum minus some inner subarray, so the best wrap = total − (minimum subarray sum). Return max(maxKadane, total − minKadane), but guard the all-negative case: if maxKadane < 0, every element is negative and 'total − min' would wrongly suggest the empty subarray, so just return maxKadane. One pass, O(n) time, O(1) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realize a circular subarray is either non-wrapping (Kadane) or wrapping (= total − minimum subarray), and whether you catch the all-negative edge case that the complement trick breaks on.

Where candidates slip

Forgetting the all-negative guard, so total − minSum returns 0 (the empty subarray) instead of the largest single negative element.

How to stand out

Derive the wrapping case as 'total minus the min subarray', run both Kadanes in a single pass, and proactively call out the all-negative edge case before the interviewer does.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Every Circular Subarray	`O(n²)`	`O(1)`	Open with this to frame the search space, then flag it as too slow for n = 3·10⁴ before pivoting to Kadane.	Read
2	Standard Kadane — Non-Wrapping Only (Building Block)	`O(n)`	`O(1)`	Establish Kadane as the tool, then immediately show it misses the wrapping case (e.g. [5,-3,5]) — motivating the full solution.	Read
3	Two-Case Kadane — max(Kadane, total − minKadane) (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'the best subarray either doesn't wrap (Kadane) or it does — and a wrap is total minus the minimum subarray', then call out the all-negative guard.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMax sum subarray in a circular arrayTry every circular subarray?YesNoExplore the full tree

Why a wrapping subarray equals total minus the middle

How to read it:A wrapping run (a prefix + a suffix) is everything EXCEPT a contiguous middle chunk. Maximizing the wrap = minimizing that excluded middle.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Try Every Circular Subarray

TimeO(n²)SpaceO(1)

Open with this to frame the search space, then flag it as too slow for n = 3·10⁴ before pivoting to Kadane.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A circular subarray is fixed by a start index and a length (1 to n). How would you sum each candidate?

2Hint 2Explore hint

For every start i, extend a running sum across up to n elements, wrapping the index with (i + k) % n, and track the best sum seen.

3Hint 3Explore hint

Reset and repeat for each start. Every non-empty circular subarray is covered exactly once.

A · Core idea

The most direct reading: a circular subarray is determined by where it starts and how long it is. So fix each start index i, then grow the subarray one element at a time — using (i + k) % n to wrap past the end — accumulating a running sum and recording the maximum.

Why this covers wrapping for free. Modular indexing means a subarray starting near the end naturally continues into the front of the array. Capping the length at n enforces the 'each index at most once' rule. No special wrap logic is needed — the % n does it.

Why this is the honest baseline. It makes 'every possible circular subarray' literally executable and is trivially correct, which is exactly what you want to state before optimizing. It also handles the non-empty requirement automatically since every candidate has length ≥ 1.

Why we don't ship it. With n up to 3·10⁴, O(n²) is ~900 million operations — too slow. And it's wasteful: as the start advances, the sums it computes overlap heavily with the previous start's work. That overlap, plus the classic Maximum Subarray connection, points straight at Kadane.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [5,-3,5]

start 0

5; 5-3=2; 2+5=7

Statebest = 7

Final result10

C · Code with teaching comments

Reference implementation previewpublic int maxSubarraySumCircular(int[] nums) { int n = nums.length; int best = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { int sum = 0;Explore the full code

solution.javaJava

Brute Force — Try Every Circular Subarray — reference

3 teaching notes

1
public int maxSubarraySumCircular(int[] nums) {
2
    int n = nums.length;
3
    int best = Integer.MIN_VALUE;
4
    for (int i = 0; i < n; i++) {
5
        int sum = 0;
6
        // Lengths 1..n only — capping at n enforces 'each index used at most once'.
7
        for (int k = 0; k < n; k++) {
8
            // Modular index wraps past the end, so circular subarrays are handled with
9
            // no special case.
10
            sum += nums[(i + k) % n];
11
            // Every prefix of this start is a valid non-empty subarray — record the
12
            // best.
13
            best = Math.max(best, sum);
14
        }
15
    }
16
    return best;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

Recomputing overlapping running sums for each start is the redundancy Kadane removes in the linear case. Recognizing that the circular problem is 'Maximum Subarray, but the buffer wraps' is the bridge: solve the two halves (wrap / no-wrap) with the linear tool you already trust.

ComplexityO(n²) time, O(1) space — There are n starting positions and up to n lengths each, with O(1) work per extension (using modular indexing), giving O(n²) total time and O(1) extra space.

E · Edge cases and pitfalls5nums = [-3,-2,-3] — Every sum is negative; best ends at -2, the largest single element — correct because we never consider an empty subarray.Explore edge cases

Edge cases handled

nums = [-3,-2,-3]Every sum is negative; best ends at -2, the largest single element — correct because we never consider an empty subarray.
nums = [3]One start, one length → returns 3.

Pitfalls

Letting k run to 2n − 1 instead of n − 1 — would reuse indices and overcount.
Initializing best to 0 — wrong for all-negative arrays (the empty-subarray bug in disguise).
Shipping O(n²) — TLEs near n = 3·10⁴.

03.2

Approach 2 of 3

Standard Kadane — Non-Wrapping Only (Building Block)

TimeO(n)SpaceO(1)

Establish Kadane as the tool, then immediately show it misses the wrapping case (e.g. [5,-3,5]) — motivating the full solution.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Recall Maximum Subarray: a running sum that resets whenever it would do better starting fresh. curMax = max(x, curMax + x).

2Hint 2Explore hint

Track the best curMax ever seen. This finds the optimal NON-wrapping subarray in one pass.

3Hint 3Explore hint

Now test it on [5,-3,5]: Kadane gives 7, but the true circular answer is 10. What case is it missing?

A · Core idea

Kadane's algorithm is the linear core. Maintain a running subarray sum curMax; at each element decide whether to extend the current subarray or start fresh at the current element: curMax = max(x, curMax + x). Track the largest curMax seen in maxSum. That value is the best non-wrapping subarray sum.

Why this is the right building block. The circular problem is just Maximum Subarray with one extra case (the wrap). Establishing the linear answer first mirrors how you'd reason on a whiteboard and gives half the final answer directly — the non-wrapping candidate.

Where it falls short. Consider [5, -3, 5]. Kadane finds 5 - 3 + 5 = 7 (the whole array) or just 5. But the best circular subarray takes the last 5, wraps around, and grabs the first 5 for 10. Kadane alone cannot see this because it only considers contiguous runs in the linear array — it never wraps.

The fix this motivates. A wrapping subarray is a suffix plus a prefix — i.e. the entire array minus a contiguous middle chunk. To maximize the wrap, minimize that excluded middle. So the full solution runs Kadane a second time to find the minimum subarray, and computes total − minSum. The next approach combines both into one pass.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [5,-3,5]

x=5

curMax = max(5, 0+5) = 5

StatemaxSum = 5

Final result7 (WRONG — true circular answer is 10)

C · Code with teaching comments

Reference implementation previewpublic int maxSubarraySumCircular(int[] nums) { int maxSum = nums[0], curMax = 0; for (int x : nums) { curMax = Math.max(x, curMax + x); maxSum = Math.max(maxSum, curMax);Explore the full code

solution.javaJava

Standard Kadane — Non-Wrapping Only (Building Block) — reference

3 teaching notes

1
public int maxSubarraySumCircular(int[] nums) {
2
    int maxSum = nums[0], curMax = 0;
3
    for (int x : nums) {
4
        // Kadane's core: extend the current run or restart at x, whichever is larger.
5
        curMax = Math.max(x, curMax + x);
6
        // Track the best non-wrapping subarray sum across the pass.
7
        maxSum = Math.max(maxSum, curMax);
8
    }
9
    // Correct for linear Maximum Subarray, but blind to wrapping runs — hence
10
    // incomplete here.
11
    return maxSum; // non-wrapping only — incomplete!
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Kadane's decision 'extend or restart' (curMax = max(x, curMax + x)) is the atomic move of all max-subarray problems. Seeing precisely what it CAN'T do — wrap around — is what tells you to add the complementary 'total minus min subarray' case rather than inventing something exotic.

ComplexityO(n) time, O(1) space — A single pass with O(1) work per element → O(n) time, O(1) space. It just doesn't cover wraps yet.

E · Edge cases and pitfalls5nums = [1,-2,3,-2] — No wrap helps here, so plain Kadane already returns the correct 3.Explore edge cases

Edge cases handled

nums = [1,-2,3,-2]No wrap helps here, so plain Kadane already returns the correct 3.
nums = [5,-3,5]Returns 7 — demonstrably wrong, exposing the missing wrap case.

Pitfalls

Initializing maxSum to 0 instead of nums[0] — breaks all-negative arrays.
Stopping here — it silently fails on any input where wrapping wins.
Initializing curMax to nums[0] AND iterating from index 0 — double-counts the first element; start curMax at 0.

03.3

Approach 3 of 3 · Optimal

Two-Case Kadane — max(Kadane, total − minKadane) (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'the best subarray either doesn't wrap (Kadane) or it does — and a wrap is total minus the minimum subarray', then call out the all-negative guard.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Split into two cases. Case 1: the best subarray doesn't wrap → plain Kadane max. Case 2: it wraps.

2Hint 2Explore hint

A wrapping subarray is the whole array minus a contiguous middle chunk. To maximize the wrap, minimize that chunk → total − (minimum subarray sum).

3Hint 3Explore hint

Run max-Kadane and min-Kadane together while summing the total. Answer = max(maxSum, total − minSum). But if maxSum < 0, every element is negative — return maxSum, because total − minSum would be the empty subarray (0).

A · Core idea

Every circular subarray is exactly one of two shapes, so we compute the best of each and take the larger.

Case 1 — the best subarray doesn't wrap. This is plain Maximum Subarray: Kadane gives maxSum, the best contiguous run within the linear array.

Case 2 — the best subarray wraps around the end. A wrapping subarray consists of a suffix nums[i..n-1] joined with a prefix nums[0..j]. Equivalently, it's the entire array minus the contiguous middle chunk nums[j+1..i-1] that it leaves out. So wrappingSum = total − middleSum. To make the wrap as large as possible, we make the excluded middle as small as possible — i.e. total − minSubarraySum, where minSubarraySum is the minimum contiguous subarray sum (a second Kadane, minimizing instead of maximizing).

Why both Kadanes run in a single pass. The max-Kadane recurrence curMax = max(x, curMax + x) and the min-Kadane recurrence curMin = min(x, curMin + x) are independent and can be updated together as we also accumulate total. One loop, three running quantities, O(1) memory.

The critical all-negative guard. If every element is negative, the minimum subarray is the whole array, so total − minSum = 0 — which corresponds to excluding everything, i.e. the empty subarray. But the problem demands a non-empty subarray. Detect this exactly when maxSum < 0 (the best non-wrapping subarray is itself negative, which only happens when all elements are negative). In that case the true answer is maxSum — the largest (least negative) single element — so we return it directly and never consult the wrap case. For [-3, -2, -3], maxSum = -2 and the guard correctly returns -2 instead of 0.

Putting it together. if maxSum < 0: return maxSum; else return max(maxSum, total − minSum). The two cases are exhaustive, each solved by an O(n) Kadane, and the guard handles the one degenerate input — a clean, complete O(n)/O(1) solution.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [5,-3,5]

Array state

min middle

min subarray is [-3] (sum -3)

[0]

-3

[1]

[2]

Current pointerResolved stateNot processed

Final result10

C · Code with teaching comments

solution.javaJava

Two-Case Kadane — max(Kadane, total − minKadane) (Optimal) — optimal

5 teaching notes

1
public int maxSubarraySumCircular(int[] nums) {
2
    int total = 0;
3
    int maxSum = nums[0], curMax = 0;
4
    int minSum = nums[0], curMin = 0;
5
    for (int x : nums) {
6
        // Max-Kadane: extend or restart for the best NON-wrapping subarray.
7
        curMax = Math.max(x, curMax + x);
8
        maxSum = Math.max(maxSum, curMax);
9
        // Min-Kadane in parallel: the smallest contiguous subarray, i.e. the cheapest
10
        // middle to exclude.
11
        curMin = Math.min(x, curMin + x);
12
        minSum = Math.min(minSum, curMin);
13
        // Accumulate the full sum; a wrapping subarray = total − (excluded middle).
14
        total += x;
15
    }
16
    // All-negative guard: maxSum < 0 means every element is negative; total − minSum
17
    // would be the empty subarray (0), which is illegal.
18
    if (maxSum < 0) {
19
        return maxSum;
20
    }
21
    // Better of the non-wrapping case and the best wrap (total minus the minimum
22
    // subarray).
23
    return Math.max(maxSum, total - minSum);
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The wrap-equals-complement idea — 'a wrapping segment is the total minus an inner segment' — converts a scary circular problem into two ordinary linear ones. Whenever a structure wraps and you want the best wrapping piece, ask 'what's the worst piece I could remove?' The all-negative guard is the reminder that complement tricks can silently admit the empty set.

ComplexityO(n) time, O(1) space — One pass maintaining running max, running min, and the total — all O(1) per element → O(n) time and O(1) space. No second array, no recursion.

E · Edge cases and pitfalls6nums = [-3,-2,-3] — maxSum = -2 < 0 → guard returns -2 (the max element), avoiding the bogus total − minSum = 0.Explore edge cases

Edge cases handled

nums = [-3,-2,-3]maxSum = -2 < 0 → guard returns -2 (the max element), avoiding the bogus total − minSum = 0.
nums = [3,1,3,2]All positive → minSum is the smallest single element, but maxSum is the whole array; max picks the full sum 9.
nums = [5,-3,5]Wrap wins: total − minSum = 7 − (−3) = 10 beats maxSum 7.

Pitfalls

Omitting the all-negative guard — returns 0 for arrays like [-3,-2,-3] instead of the max element.
Initializing maxSum/minSum to 0 instead of nums[0] — corrupts both Kadanes on all-negative or all-positive inputs.
Computing total − minSum where minSum spans the whole array without the guard — that's the empty-subarray bug.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int maxSubarraySumCircular(int[] nums) { int total = 0; int maxSum = nums[0], curMax = 0; int minSum = nums[0], curMin = 0; for (int x : nums) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the all-negative guard

When every element is negative, the minimum subarray is the entire array, so total − minSum = 0 — the empty subarray, which is forbidden. Without the guard you return 0 instead of the max (least-negative) element.

Explore the code comparison

Don't write this

return Math.max(maxSum, total - minSum);

Write this instead

if (maxSum < 0) {
    return maxSum;
}
return Math.max(maxSum, total - minSum);

Plain Kadane ignores wrapping

Standard Maximum Subarray only considers contiguous runs in the linear array, so it can't capture a suffix+prefix wrap. You must add the total − minSubarray case.

Explore the code comparison

Don't write this

return max_sum  # only the non-wrapping case

Write this instead

if max_sum < 0:
    return max_sum
return max(max_sum, total - min_sum)

Wrong initial values for the running extrema

Seeding maxSum or minSum at 0 assumes an empty subarray is allowed and biases all-negative / all-positive inputs. Seed them with nums[0] and start the running curMax/curMin at 0.

Explore the code comparison

Don't write this

int maxSum = 0, minSum = 0;

Write this instead

int maxSum = nums[0], minSum = nums[0];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Kadane twice — max subarray and total minus min subarray

Code pattern to memorize

maxSum = Kadane_max(nums)
minSum = Kadane_min(nums)
total  = sum(nums)
if maxSum < 0: return maxSum   # all negative
return max(maxSum, total - minSum)

Rules to remember

1The answer is the better of two cases: a non-wrapping subarray (plain Kadane) or a wrapping one.
2A wrapping subarray = total − (the inner non-wrapping subarray it excludes), so its max is total − minSubarraySum.
3Guard the all-negative array: if the max subarray sum is < 0, return it directly — total − minSum collapses to the empty subarray (value 0), which is illegal.
4Run two Kadanes in one pass: track running max and running min simultaneously while accumulating the total.
5The subarray must be non-empty; the empty-subarray trap is exactly what the all-negative guard prevents.

Use this pattern when

Maximum/minimum subarray sum where the array wraps around (circular)
You already know Kadane and the array is a ring buffer
A 'best contiguous segment' problem with end-to-front continuity
Any problem reducible to 'total minus the worst middle chunk'

Choose another pattern when

Array is linear, not circular → plain Kadane is enough
You need the subarray indices, not just the sum → track boundaries during Kadane
Elements can be reused / it's a subsequence → different DP
You need max product, not sum → Maximum Product Subarray (track min and max factors)

Interview takeaway

Maximum Sum Circular Subarray is Kadane with a twist: the wrapping case is just total minus the minimum subarray. Running max- and min-Kadane together in one pass — plus the all-negative guard — is the whole trick. The 'total − worst middle' complement idea recurs whenever a structure wraps.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternKadane with a complement twist. Recognize it when 'maximum subarray' meets a circular buffer: the answer is max(plain Kadane, total − minimum subarray), guarded against the all-negative empty-subarray case. The 'total minus the worst middle' idea reappears wherever a structure wraps; the dual max/min Kadane recurs in Maximum Product Subarray.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Subarray
Coming soon
The linear core — plain Kadane, no wrap. This problem is that one plus the total − min case.
Maximum Product Subarray
Kadane variant tracking BOTH running max and min because a negative factor flips them.
Maximum Subarray Sum with One Deletion
Coming soon
Two-state Kadane: best ending here with zero or one deletion used.
Substring With Largest Variance
Coming soon
Reframes a counting problem as Kadane over a transformed +1/-1 array.

Same pattern

←

Maximal Square

Continue · Next problem

Minimum Path Sum

mediumDynamic ProgrammingLC #918Sometimes asked

Maximum Sum Circular Subarray

LCPractice

Dynamic Programming · 16 of 44 · 10 min

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: formally, the next element of nums[i] is nums[(i + 1) % n].

In plain English

Examples

Example 1

Input: nums = [1,-2,3,-2]
Output: 3
Note: The non-wrapping subarray [3] gives 3 — wrapping doesn't help here.

Example 2

Input: nums = [5,-3,5]
Output: 10
Note: The wrapping subarray [5, (wrap), 5] sums to 10, beating the best non-wrapping run (5-3+5 = 7).

Example 3

Input: nums = [-3,-2,-3]
Output: -2
Note: All negative — the answer is the largest single element, -2. The total-minus-min trick must NOT return 0.

Constraints

n == nums.length
1 ≤ n ≤ 3 × 10⁴
-3 × 10⁴ ≤ nums[i] ≤ 3 × 10⁴
The subarray must be non-empty and use each buffer index at most once

Clarifying questions4First question: Can the subarray wrap around the end?Explore questions

Q1.Can the subarray wrap around the end?
Yes — that's the whole point. A run like nums[n-1], nums[0], nums[1] is valid. Without wrapping this is plain Maximum Subarray.
Q2.Must the subarray be non-empty?
Yes. This matters enormously: when every element is negative the answer is the largest (least negative) single element, not 0.
Q3.Can an element be used more than once?
No. Even though it's circular, each buffer index appears at most once, so a wrapping subarray can't be longer than n.
Q4.Are all elements possibly negative?
Yes, and that's the key edge case. The total-minus-min trick must be guarded, or it returns 0 (the empty subarray) instead of the max element.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Forgetting the all-negative guard, so total − minSum returns 0 (the empty subarray) instead of the largest single negative element.

How to stand out

Derive the wrapping case as 'total minus the min subarray', run both Kadanes in a single pass, and proactively call out the all-negative edge case before the interviewer does.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Try Every Circular Subarray	`O(n²)`	`O(1)`	Open with this to frame the search space, then flag it as too slow for n = 3·10⁴ before pivoting to Kadane.	Read
2	Standard Kadane — Non-Wrapping Only (Building Block)	`O(n)`	`O(1)`	Establish Kadane as the tool, then immediately show it misses the wrapping case (e.g. [5,-3,5]) — motivating the full solution.	Read
3	Two-Case Kadane — max(Kadane, total − minKadane) (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'the best subarray either doesn't wrap (Kadane) or it does — and a wrap is total minus the minimum subarray', then call out the all-negative guard.	Read

Why a wrapping subarray equals total minus the middle

How to read it:A wrapping run (a prefix + a suffix) is everything EXCEPT a contiguous middle chunk. Maximizing the wrap = minimizing that excluded middle.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Try Every Circular Subarray

TimeO(n²)SpaceO(1)

Open with this to frame the search space, then flag it as too slow for n = 3·10⁴ before pivoting to Kadane.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A circular subarray is fixed by a start index and a length (1 to n). How would you sum each candidate?

2Hint 2Explore hint

For every start i, extend a running sum across up to n elements, wrapping the index with (i + k) % n, and track the best sum seen.

3Hint 3Explore hint

Reset and repeat for each start. Every non-empty circular subarray is covered exactly once.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [5,-3,5]

start 0

5; 5-3=2; 2+5=7

Statebest = 7

Final result10

C · Code with teaching comments

Reference implementation previewpublic int maxSubarraySumCircular(int[] nums) { int n = nums.length; int best = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { int sum = 0;Explore the full code

solution.javaJava

Brute Force — Try Every Circular Subarray — reference

3 teaching notes

1
public int maxSubarraySumCircular(int[] nums) {
2
    int n = nums.length;
3
    int best = Integer.MIN_VALUE;
4
    for (int i = 0; i < n; i++) {
5
        int sum = 0;
6
        // Lengths 1..n only — capping at n enforces 'each index used at most once'.
7
        for (int k = 0; k < n; k++) {
8
            // Modular index wraps past the end, so circular subarrays are handled with
9
            // no special case.
10
            sum += nums[(i + k) % n];
11
            // Every prefix of this start is a valid non-empty subarray — record the
12
            // best.
13
            best = Math.max(best, sum);
14
        }
15
    }
16
    return best;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5nums = [-3,-2,-3] — Every sum is negative; best ends at -2, the largest single element — correct because we never consider an empty subarray.Explore edge cases

Edge cases handled

nums = [-3,-2,-3]Every sum is negative; best ends at -2, the largest single element — correct because we never consider an empty subarray.
nums = [3]One start, one length → returns 3.

Pitfalls

Letting k run to 2n − 1 instead of n − 1 — would reuse indices and overcount.
Initializing best to 0 — wrong for all-negative arrays (the empty-subarray bug in disguise).
Shipping O(n²) — TLEs near n = 3·10⁴.

03.2

Approach 2 of 3

Standard Kadane — Non-Wrapping Only (Building Block)

TimeO(n)SpaceO(1)

Establish Kadane as the tool, then immediately show it misses the wrapping case (e.g. [5,-3,5]) — motivating the full solution.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Recall Maximum Subarray: a running sum that resets whenever it would do better starting fresh. curMax = max(x, curMax + x).

2Hint 2Explore hint

Track the best curMax ever seen. This finds the optimal NON-wrapping subarray in one pass.

3Hint 3Explore hint

Now test it on [5,-3,5]: Kadane gives 7, but the true circular answer is 10. What case is it missing?

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [5,-3,5]

x=5

curMax = max(5, 0+5) = 5

StatemaxSum = 5

Final result7 (WRONG — true circular answer is 10)

C · Code with teaching comments

solution.javaJava

Standard Kadane — Non-Wrapping Only (Building Block) — reference

3 teaching notes

1
public int maxSubarraySumCircular(int[] nums) {
2
    int maxSum = nums[0], curMax = 0;
3
    for (int x : nums) {
4
        // Kadane's core: extend the current run or restart at x, whichever is larger.
5
        curMax = Math.max(x, curMax + x);
6
        // Track the best non-wrapping subarray sum across the pass.
7
        maxSum = Math.max(maxSum, curMax);
8
    }
9
    // Correct for linear Maximum Subarray, but blind to wrapping runs — hence
10
    // incomplete here.
11
    return maxSum; // non-wrapping only — incomplete!
12
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.12 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — A single pass with O(1) work per element → O(n) time, O(1) space. It just doesn't cover wraps yet.

E · Edge cases and pitfalls5nums = [1,-2,3,-2] — No wrap helps here, so plain Kadane already returns the correct 3.Explore edge cases

Edge cases handled

nums = [1,-2,3,-2]No wrap helps here, so plain Kadane already returns the correct 3.
nums = [5,-3,5]Returns 7 — demonstrably wrong, exposing the missing wrap case.

Pitfalls

Initializing maxSum to 0 instead of nums[0] — breaks all-negative arrays.
Stopping here — it silently fails on any input where wrapping wins.
Initializing curMax to nums[0] AND iterating from index 0 — double-counts the first element; start curMax at 0.

03.3

Approach 3 of 3 · Optimal

Two-Case Kadane — max(Kadane, total − minKadane) (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'the best subarray either doesn't wrap (Kadane) or it does — and a wrap is total minus the minimum subarray', then call out the all-negative guard.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Split into two cases. Case 1: the best subarray doesn't wrap → plain Kadane max. Case 2: it wraps.

2Hint 2Explore hint

A wrapping subarray is the whole array minus a contiguous middle chunk. To maximize the wrap, minimize that chunk → total − (minimum subarray sum).

3Hint 3Explore hint

A · Core idea

Every circular subarray is exactly one of two shapes, so we compute the best of each and take the larger.

Case 1 — the best subarray doesn't wrap. This is plain Maximum Subarray: Kadane gives maxSum, the best contiguous run within the linear array.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [5,-3,5]

Array state

min middle

min subarray is [-3] (sum -3)

[0]

-3

[1]

[2]

Current pointerResolved stateNot processed

Final result10

C · Code with teaching comments

solution.javaJava

Two-Case Kadane — max(Kadane, total − minKadane) (Optimal) — optimal

5 teaching notes

1
public int maxSubarraySumCircular(int[] nums) {
2
    int total = 0;
3
    int maxSum = nums[0], curMax = 0;
4
    int minSum = nums[0], curMin = 0;
5
    for (int x : nums) {
6
        // Max-Kadane: extend or restart for the best NON-wrapping subarray.
7
        curMax = Math.max(x, curMax + x);
8
        maxSum = Math.max(maxSum, curMax);
9
        // Min-Kadane in parallel: the smallest contiguous subarray, i.e. the cheapest
10
        // middle to exclude.
11
        curMin = Math.min(x, curMin + x);
12
        minSum = Math.min(minSum, curMin);
13
        // Accumulate the full sum; a wrapping subarray = total − (excluded middle).
14
        total += x;
15
    }
16
    // All-negative guard: maxSum < 0 means every element is negative; total − minSum
17
    // would be the empty subarray (0), which is illegal.
18
    if (maxSum < 0) {
19
        return maxSum;
20
    }
21
    // Better of the non-wrapping case and the best wrap (total minus the minimum
22
    // subarray).
23
    return Math.max(maxSum, total - minSum);
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — One pass maintaining running max, running min, and the total — all O(1) per element → O(n) time and O(1) space. No second array, no recursion.

E · Edge cases and pitfalls6nums = [-3,-2,-3] — maxSum = -2 < 0 → guard returns -2 (the max element), avoiding the bogus total − minSum = 0.Explore edge cases

Edge cases handled

nums = [-3,-2,-3]maxSum = -2 < 0 → guard returns -2 (the max element), avoiding the bogus total − minSum = 0.
nums = [3,1,3,2]All positive → minSum is the smallest single element, but maxSum is the whole array; max picks the full sum 9.
nums = [5,-3,5]Wrap wins: total − minSum = 7 − (−3) = 10 beats maxSum 7.

Pitfalls

Omitting the all-negative guard — returns 0 for arrays like [-3,-2,-3] instead of the max element.
Initializing maxSum/minSum to 0 instead of nums[0] — corrupts both Kadanes on all-negative or all-positive inputs.
Computing total − minSum where minSum spans the whole array without the guard — that's the empty-subarray bug.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int maxSubarraySumCircular(int[] nums) { int total = 0; int maxSum = nums[0], curMax = 0; int minSum = nums[0], curMin = 0; for (int x : nums) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Missing the all-negative guard

Explore the code comparison

Don't write this

return Math.max(maxSum, total - minSum);

Write this instead

if (maxSum < 0) {
    return maxSum;
}
return Math.max(maxSum, total - minSum);

Plain Kadane ignores wrapping

Standard Maximum Subarray only considers contiguous runs in the linear array, so it can't capture a suffix+prefix wrap. You must add the total − minSubarray case.

Explore the code comparison

Don't write this

return max_sum  # only the non-wrapping case

Write this instead

if max_sum < 0:
    return max_sum
return max(max_sum, total - min_sum)

Wrong initial values for the running extrema

Seeding maxSum or minSum at 0 assumes an empty subarray is allowed and biases all-negative / all-positive inputs. Seed them with nums[0] and start the running curMax/curMin at 0.

Explore the code comparison

Don't write this

int maxSum = 0, minSum = 0;

Write this instead

int maxSum = nums[0], minSum = nums[0];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Kadane twice — max subarray and total minus min subarray

Code pattern to memorize

maxSum = Kadane_max(nums)
minSum = Kadane_min(nums)
total  = sum(nums)
if maxSum < 0: return maxSum   # all negative
return max(maxSum, total - minSum)

Rules to remember

1The answer is the better of two cases: a non-wrapping subarray (plain Kadane) or a wrapping one.
2A wrapping subarray = total − (the inner non-wrapping subarray it excludes), so its max is total − minSubarraySum.
3Guard the all-negative array: if the max subarray sum is < 0, return it directly — total − minSum collapses to the empty subarray (value 0), which is illegal.
4Run two Kadanes in one pass: track running max and running min simultaneously while accumulating the total.
5The subarray must be non-empty; the empty-subarray trap is exactly what the all-negative guard prevents.

Use this pattern when

Maximum/minimum subarray sum where the array wraps around (circular)
You already know Kadane and the array is a ring buffer
A 'best contiguous segment' problem with end-to-front continuity
Any problem reducible to 'total minus the worst middle chunk'

Choose another pattern when

Array is linear, not circular → plain Kadane is enough
You need the subarray indices, not just the sum → track boundaries during Kadane
Elements can be reused / it's a subsequence → different DP
You need max product, not sum → Maximum Product Subarray (track min and max factors)

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Subarray
Coming soon
The linear core — plain Kadane, no wrap. This problem is that one plus the total − min case.
Maximum Product Subarray
Kadane variant tracking BOTH running max and min because a negative factor flips them.
Maximum Subarray Sum with One Deletion
Coming soon
Two-state Kadane: best ending here with zero or one deletion used.
Substring With Largest Variance
Coming soon
Reframes a counting problem as Kadane over a transformed +1/-1 array.

Same pattern

←

Maximal Square

Continue · Next problem

Minimum Path Sum