Maximum Sum Circular Subarray (LeetCode 918)
You get an integer array nums that is circular: the number after the last one is the first one again. A subarray is a run of numbers that sit next to each other, and it may wrap around the end.
Find the largest sum of a non-empty subarray. A subarray can use each position at most once.
Worked Examples
nums = [1,-2,3,-2]3[3] has the largest sum, 3.nums = [5,-3,5]10[5, 5] wraps around from the last number to the first, and its sum is 10.nums = [-3,-2,-3]-2-2.⚖️Formal Constraints & Bounds
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104
Core Insight
A run that wraps around the end is the whole array without one plain run in the middle, so the best wrapping run is the total minus the worst plain run: run Kadane's Algorithm once for the best and once, mirrored, for the worst.
Real-World Scenario & Production Applications
Any repeating cycle, such as a day of hourly profits that is followed by the same day again: the best stretch may start in the evening and continue into the next morning.
Step-by-Step Execution Trace Table
Trace of Example 2: nums = [5, -3, 5]. curr_max, curr_min, best and worst start at 5, and total = 5.
x | curr_max | best | curr_min | worst | total |
|---|---|---|---|---|---|
| -3 | 2 | 5 | -3 | -3 | 2 |
| 5 | 7 | 7 | 2 | -3 | 7 |
The best plain run is 7. The worst plain run is -3, so the best wrapping run is total - worst = 7 - (-3) = 10. The answer is max(7, 10) = 10.
| 1 | total = curr_max = curr_min = best = worst = nums[0] |
| 2 | for x in nums[1:]: |
| 3 | curr_max = max(x, curr_max + x); curr_min = min(x, curr_min + x) |
| 4 | best = max(best, curr_max); worst = min(worst, curr_min); total += x |
| 5 | return max(best, total - worst) if best > 0 else best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
In a circular array, the last number is followed by the first. A subarray is now either a plain run, or a run that wraps around the end. A run that wraps around is the whole array without one plain run in the middle. So the best wrapping run is the total minus the worst plain run.
➗ What Is Added To Kadane
Kadane's Algorithm finds the best plain run. This variant runs it a second time with min to find the worst plain run, and adds a running total. The answer is the larger of the best plain run and total - worst.
🔑 The Key Idea in the Code
If every number is negative, the worst plain run is the whole array, so total - worst is 0, which is an empty run. An empty run is not allowed, so when best is not positive the answer is best.
Treating the wrap as a second pass: a wrapping run is the total minus one plain run in the middle. Do not extend the array or loop twice.
Removing the best run instead of the worst:
total - bestis the part left over from the best run, not the best wrapping run. Remove the worst plain run.Ignoring the all-negative array: the worst plain run is then the whole array,
total - worstis an empty run, and the answer would be 0 instead of the largest negative number.Forgetting to run the mirror of Kadane:
worstneeds its owncurr_minwithmin, notbestwith a negative sign.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The array is circular" and "a subarray may wrap around": the best run is a plain run, or a run that holds the end and the start. A best sum over contiguous runs points to Kadane's Algorithm, and the wrap is the part that is new.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
best and worst are the best and the worst sum of a plain subarray, each found with the extend-or-restart rule. A wrapping run is total minus a plain run in the middle, so its best value is total - worst.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting the wrap: returning only
bestmisses[5, -3, 5], where the answer wraps around.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Kadane's Algorithm run twice. A run in a circular array is either a plain run or one that wraps around the end, and a wrapping run is the whole array minus a plain run in the middle. So I run Kadane once with max for the best plain run, and once with min for the worst plain run, and I keep the total. The answer is the larger of the best plain run and the total minus the worst plain run. If every number is negative, the worst plain run is the whole array and the wrapping run would be empty, so I return the best plain run. That is one pass, order N time and order 1 space.
Complexity & Mathematical Proof
O(N)
Look at the loop. for x in nums[1:] visits each number once. Each visit updates curr_max, curr_min, best, worst and total, which is constant work. That is N steps, so time is O(N).
O(1)
The code keeps six variables, whatever the length of nums is. The circular array is never copied or doubled, so space is O(1).
Derivation Progression
for x in nums[1:] visits each number after the first once.
5 = O(1)
Two extend-or-restart steps, two global updates and one addition to the total.
5N = O(N)
Numbers times a constant amount of work.
Variable Definitions
Length of nums
Best sum of a plain subarray
Worst sum of a plain subarray
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables total, curr_max, curr_min, best and worst
O(1): one integer
Boundary Best / Worst Cases
: the loop always visits every number.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "circular array", "largest sum of a non-empty subarray". A best sum over runs is Kadane's Algorithm, and "circular" adds the runs that wrap around the end.
, so a loop over all start positions and lengths is steps. One pass is , and the sums stay below , which fits in 32 bits.
When every number is negative, total - worst is 0 because the worst plain run is the whole array, and a 0 would mean an empty run. Guard it with best > 0. Doubling the array and running Kadane on it is wrong without a length limit, because a run could use a position twice.
Maximum Sum Circular Subarray (LeetCode 918)
You get an integer array nums that is circular: the number after the last one is the first one again. A subarray is a run of numbers that sit next to each other, and it may wrap around the end.
Find the largest sum of a non-empty subarray. A subarray can use each position at most once.
Worked Examples
nums = [1,-2,3,-2]3[3] has the largest sum, 3.nums = [5,-3,5]10[5, 5] wraps around from the last number to the first, and its sum is 10.nums = [-3,-2,-3]-2-2.⚖️Formal Constraints & Bounds
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104
Core Insight
A run that wraps around the end is the whole array without one plain run in the middle, so the best wrapping run is the total minus the worst plain run: run Kadane's Algorithm once for the best and once, mirrored, for the worst.
Real-World Scenario & Production Applications
Any repeating cycle, such as a day of hourly profits that is followed by the same day again: the best stretch may start in the evening and continue into the next morning.
Step-by-Step Execution Trace Table
Trace of Example 2: nums = [5, -3, 5]. curr_max, curr_min, best and worst start at 5, and total = 5.
x | curr_max | best | curr_min | worst | total |
|---|---|---|---|---|---|
| -3 | 2 | 5 | -3 | -3 | 2 |
| 5 | 7 | 7 | 2 | -3 | 7 |
The best plain run is 7. The worst plain run is -3, so the best wrapping run is total - worst = 7 - (-3) = 10. The answer is max(7, 10) = 10.
| 1 | total = curr_max = curr_min = best = worst = nums[0] |
| 2 | for x in nums[1:]: |
| 3 | curr_max = max(x, curr_max + x); curr_min = min(x, curr_min + x) |
| 4 | best = max(best, curr_max); worst = min(worst, curr_min); total += x |
| 5 | return max(best, total - worst) if best > 0 else best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
In a circular array, the last number is followed by the first. A subarray is now either a plain run, or a run that wraps around the end. A run that wraps around is the whole array without one plain run in the middle. So the best wrapping run is the total minus the worst plain run.
➗ What Is Added To Kadane
Kadane's Algorithm finds the best plain run. This variant runs it a second time with min to find the worst plain run, and adds a running total. The answer is the larger of the best plain run and total - worst.
🔑 The Key Idea in the Code
If every number is negative, the worst plain run is the whole array, so total - worst is 0, which is an empty run. An empty run is not allowed, so when best is not positive the answer is best.
Treating the wrap as a second pass: a wrapping run is the total minus one plain run in the middle. Do not extend the array or loop twice.
Removing the best run instead of the worst:
total - bestis the part left over from the best run, not the best wrapping run. Remove the worst plain run.Ignoring the all-negative array: the worst plain run is then the whole array,
total - worstis an empty run, and the answer would be 0 instead of the largest negative number.Forgetting to run the mirror of Kadane:
worstneeds its owncurr_minwithmin, notbestwith a negative sign.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The array is circular" and "a subarray may wrap around": the best run is a plain run, or a run that holds the end and the start. A best sum over contiguous runs points to Kadane's Algorithm, and the wrap is the part that is new.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
best and worst are the best and the worst sum of a plain subarray, each found with the extend-or-restart rule. A wrapping run is total minus a plain run in the middle, so its best value is total - worst.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting the wrap: returning only
bestmisses[5, -3, 5], where the answer wraps around.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Kadane's Algorithm run twice. A run in a circular array is either a plain run or one that wraps around the end, and a wrapping run is the whole array minus a plain run in the middle. So I run Kadane once with max for the best plain run, and once with min for the worst plain run, and I keep the total. The answer is the larger of the best plain run and the total minus the worst plain run. If every number is negative, the worst plain run is the whole array and the wrapping run would be empty, so I return the best plain run. That is one pass, order N time and order 1 space.
Complexity & Mathematical Proof
O(N)
Look at the loop. for x in nums[1:] visits each number once. Each visit updates curr_max, curr_min, best, worst and total, which is constant work. That is N steps, so time is O(N).
O(1)
The code keeps six variables, whatever the length of nums is. The circular array is never copied or doubled, so space is O(1).
Derivation Progression
for x in nums[1:] visits each number after the first once.
5 = O(1)
Two extend-or-restart steps, two global updates and one addition to the total.
5N = O(N)
Numbers times a constant amount of work.
Variable Definitions
Length of nums
Best sum of a plain subarray
Worst sum of a plain subarray
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables total, curr_max, curr_min, best and worst
O(1): one integer
Boundary Best / Worst Cases
: the loop always visits every number.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "circular array", "largest sum of a non-empty subarray". A best sum over runs is Kadane's Algorithm, and "circular" adds the runs that wrap around the end.
, so a loop over all start positions and lengths is steps. One pass is , and the sums stay below , which fits in 32 bits.
When every number is negative, total - worst is 0 because the worst plain run is the whole array, and a 0 would mean an empty run. Guard it with best > 0. Doubling the array and running Kadane on it is wrong without a length limit, because a run could use a position twice.