What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Dynamic Programming

Builds on Kadane's Algorithm, which you haven’t finished yet.

P2MediumBuilt on Linear DP~4 min speedrun

Kadane's Algorithm on a Circular Array (Maximum Sum Circular Subarray)

Built on

Kadane's AlgorithmA run may wrap around the end, and that run is the total minus the worst plain run, so run Kadane a second time with min and keep the total.

The problem

Maximum Sum Circular Subarray (LC 918)(opens leetcode.com)

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.

Example 1

Input:nums = [1,-2,3,-2]

Output:3

The subarray [3] has the largest sum, 3.

Circular Kadane

best plain run, or total - worst plain run ➔ Kadane twice, once with max and once with min ➔ guard the all-negative array

Spot it when: You need the best sum of one unbroken run of a circular array, where the run may wrap around from the end to the start.

Circular Kadane

Python

1	def max_subarray_circular(nums: list[int]) -> int:
2	"""Maximum Sum Circular Subarray: the best plain run, or the total minus the worst plain run.
3	Time: O(N) \| Space: O(1)
4	"""
5	# best, worst: the best and the worst sum of a plain subarray; curr_max, curr_min: the same for one that ends at the current number
6	total = curr_max = curr_min = best = worst = nums[0]
7	for x in nums[1:]:
8	# 1. Run Kadane For The Best And For The Worst:
9	# The same extend-or-restart rule, once with max for the best run and once with min for the worst run.
10	curr_max = max(x, curr_max + x)
11	curr_min = min(x, curr_min + x)
12	best = max(best, curr_max)
13	worst = min(worst, curr_min)
14	total += x
15
16	# 2. Choose The Plain Run Or The Wrapping Run:
17	# A run that wraps around is the total minus a plain run in the middle, so remove the worst plain run.
18	# If every number is negative, the worst plain run is the whole array and the wrapping run would be empty, so keep best.
19	return max(best, total - worst) if best > 0 else best

Invariant: After each x, best and worst are the best and the worst sum of a plain subarray so far, and total is the sum of the numbers seen.

A run in a circular array is a plain run, or it wraps around the end, and a wrapping run is the whole array without one plain run in the middle. So run Kadane's Algorithm twice, once with max for best and once with min for worst, keep total, and the answer is the larger of best and total - worst. The trap is an array of only negative numbers: worst is then the whole array, total - worst is 0, and that is an empty run, so return best when it is not positive.

See it run

Circular Kadane, step by step

curr_max -2curr_min -2best -2worst -2total -2

Each column is one index of nums. The rows curr_max and curr_min fill in as the steps run.

x the number being read
curr_max the largest sum of a run that ends at x
curr_min the smallest sum of a run that ends at x

Start: total, curr_max, curr_min, best and worst are all nums[0] = -2.

nums

-2x

-5

curr_max

-2curr_max

curr_min

-2curr_min

1 / 8

Gotchas1 of 3

The trap
Gotcha 1: Taking total - worst when every number is negative
Mistake
```
return max(best, total - worst)
```
Fix
```
return max(best, total - worst) if best > 0 else best
```
What happens: When every number is negative, the worst plain run is the whole array, so total - worst is 0. That would be an empty run, which is not allowed. The answer is the largest single number, which best already holds.
Example: Maximum Sum Circular Subarray (LC 918): nums = [-3, -2, -3]
Mistake: returns 0Fix: returns -2
Gotcha 2: Removing the best run instead of the worst
Mistake
```
return max(best, total - best) if best > 0 else best
```
Fix
```
return max(best, total - worst) if best > 0 else best
```
What happens: A wrapping run is everything except one plain run in the middle. To make the wrapping run as large as possible, remove the plain run with the smallest sum, the worst one. Removing the best run leaves the smallest piece.
Example: Maximum Sum Circular Subarray (LC 918): nums = [5, -3, 5]
Mistake: returns 7Fix: returns 10
Gotcha 3: Returning only the best plain run
Mistake
```
return best
```
Fix
```
return max(best, total - worst) if best > 0 else best
```
What happens: The best run may wrap around the end. A plain Kadane pass never joins the last numbers to the first ones, so it misses a run such as the two 5s around the -3.
Example: Maximum Sum Circular Subarray (LC 918): nums = [5, -3, 5]
Mistake: returns 7Fix: returns 10

Not this one if…

The array is not circular, so a run never wraps around the end and one Kadane pass is enough, as in Maximum Subarray (LC 53). See Kadane's Algorithm

Deep Dive

Why a wrapping run is the total minus a plain run

In a circular array, the last number is followed by the first number. A run can start near the end and continue at the start. Such a run wraps around.

Place the array on a circle and choose a run. The numbers that are not in the run form one unbroken piece of the circle. If the run wraps around the end of the list, that remaining piece lies inside the list, in the middle. It is a plain subarray.

So the sum of a wrapping run is total minus the sum of a plain run in the middle. To make the wrapping run as large as possible, remove the plain run with the smallest sum. That sum is worst.

Example: for nums = [5, -3, 5], total is 7 and worst is -3. The wrapping run has the sum 7 - (-3) = 10. It is the two 5s that touch at the wrap. A plain pass finds only 7.

Two Kadane passes in one loop

Maximum Subarray (LC 53) taught the extend-or-restart rule with max. The same rule with min gives the smallest sum of a subarray that ends at x. The blueprint keeps curr_max and curr_min, and it updates best and worst from them.

Both passes use the same loop, so the time stays O(N). total adds one more number per step. The space is O(1), with five variables.

The answer is max(best, total - worst). best covers the runs that do not wrap. total - worst covers the runs that wrap.

Trace for nums = [5, -3, 5]: best is 7, worst is -3 and total is 7. The answer is max(7, 10) = 10.

The empty run and the guard

If the removed plain run is the whole array, then total - worst is 0. That is an empty run, and a run must hold at least one number.

This happens when every number is negative. Then worst is the whole array. The correct answer is the largest single number, which is best.

The guard if best > 0 else best handles it. If best is positive, an empty run (value 0) can never be larger than best, so max(best, total - worst) is safe. If best is 0 or negative, return best.

Example: for [-3, -2, -3], total is -8, worst is -8, and the answer is -2. For the single number [-5], the answer is -5.

Checks and a related problem

I compared max_subarray_circular with a brute force that tries every start and every length on the circle. They agreed on 10,000 random arrays of 1 to 9 numbers, including arrays of only negative numbers and arrays of one number.

Example with a longer wrap: nums = [-2, 4, -5, 4, -5, 9, 4] has best = 13, worst = -6 and total = 9. The answer is max(13, 9 + 6) = 15. The run is 9, 4, -2, 4, which wraps around the end.

Maximum Absolute Sum of Any Subarray (LC 1749) uses the same two passes. The answer is max(best, -worst), because the absolute value of the smallest sum can be the largest.

60-Second Pitch

"A run in a circular array either stays inside the list or wraps around the end. If it wraps, the numbers outside the run form one plain piece in the middle. So a wrapping run is total minus a plain subarray, and the largest one removes the smallest plain subarray. I run Kadane's Algorithm twice in one loop, with max for best and with min for worst, and I add up total. The answer is max(best, total - worst). If every number is negative, total - worst is an empty run, so I return best. The time is O(N) and the space is O(1)."

Common Questions

Why does removing the smallest plain run give the best wrapping run?: A wrapping run is the whole circle without one plain run in the middle of the list. Its sum is total minus the sum of that plain run. To make the result as large as possible, remove the plain run with the smallest sum, which is worst.
What does the function return when every number is negative?: The largest single number, which is best. Then worst is the whole array, so total - worst is 0. That would be an empty run, which is not allowed. For [-3, -2, -3], the answer is -2.
What is the time and space complexity?: O(N) time, because one loop runs both Kadane passes and the total. O(1) space, because the function keeps five numbers.
What if the array has only one number?: The loop does not run. best, worst and total all equal nums[0]. If it is positive, total - worst is 0 and best wins. If it is not positive, the guard returns best. For [-5], the answer is -5.
How does Maximum Absolute Sum of Any Subarray (LC 1749) relate to this card?: It uses the same two Kadane passes without the total. The largest absolute sum is the larger of best and -worst. The array is not circular there, so no wrap-around case exists.

SWE Reasoning

Spot it

The question asks for the best sum of one unbroken run of an array.
The array is circular: the last number is followed by the first number.
Plain Kadane's Algorithm fails on a small example such as [5, -3, 5].
The numbers can be negative, so the whole array is not always the best run.
The answer is a sum or a similar value that can be computed as a total minus a middle part.

The invariant, step by step

Before the loop, all five variables start at nums[0]. Only one subarray ends at index 0.
For each x, curr_max and curr_min apply the extend-or-restart rule with max and with min.
best keeps the largest curr_max and worst keeps the smallest curr_min. total adds x.
After the loop, best is the best plain run and worst is the worst plain run.
A run that wraps is total - worst. A run that does not wrap is best.
If best is not positive, total - worst may be an empty run. In that case the function returns best.

Traps

Missing guard. When every number is negative, total - worst is 0, an empty run. For [-3, -2, -3], the result is 0 instead of -2. For [-5], it is 0 instead of -5.
Subtracting best and not worst. The wrapping run needs the smallest middle part removed. See the card's gotcha for [5, -3, 5].
Plain Kadane only. It never joins the end to the start.
Starting at 0. Starting best or worst at 0 allows an empty run. Start all variables at nums[0].

Practice

Canonical LeetCode:Maximum Sum Circular Subarray (LC 918)Maximum Absolute Sum of Any Subarray (LC 1749)

Theory Context•Dynamic Programming

Builds on Kadane's Algorithm, which you haven’t finished yet.

P2MediumBuilt on Linear DP~4 min speedrun

Kadane's Algorithm on a Circular Array (Maximum Sum Circular Subarray)

Built on

Kadane's AlgorithmA run may wrap around the end, and that run is the total minus the worst plain run, so run Kadane a second time with min and keep the total.

The problem

Maximum Sum Circular Subarray (LC 918)(opens leetcode.com)

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.

Example 1

Input:nums = [1,-2,3,-2]

Output:3

The subarray [3] has the largest sum, 3.

Circular Kadane

best plain run, or total - worst plain run ➔ Kadane twice, once with max and once with min ➔ guard the all-negative array

Spot it when: You need the best sum of one unbroken run of a circular array, where the run may wrap around from the end to the start.

Circular Kadane

Python

1	def max_subarray_circular(nums: list[int]) -> int:
2	"""Maximum Sum Circular Subarray: the best plain run, or the total minus the worst plain run.
3	Time: O(N) \| Space: O(1)
4	"""
5	# best, worst: the best and the worst sum of a plain subarray; curr_max, curr_min: the same for one that ends at the current number
6	total = curr_max = curr_min = best = worst = nums[0]
7	for x in nums[1:]:
8	# 1. Run Kadane For The Best And For The Worst:
9	# The same extend-or-restart rule, once with max for the best run and once with min for the worst run.
10	curr_max = max(x, curr_max + x)
11	curr_min = min(x, curr_min + x)
12	best = max(best, curr_max)
13	worst = min(worst, curr_min)
14	total += x
15
16	# 2. Choose The Plain Run Or The Wrapping Run:
17	# A run that wraps around is the total minus a plain run in the middle, so remove the worst plain run.
18	# If every number is negative, the worst plain run is the whole array and the wrapping run would be empty, so keep best.
19	return max(best, total - worst) if best > 0 else best

Invariant: After each x, best and worst are the best and the worst sum of a plain subarray so far, and total is the sum of the numbers seen.

See it run

Circular Kadane, step by step

curr_max -2curr_min -2best -2worst -2total -2

Each column is one index of nums. The rows curr_max and curr_min fill in as the steps run.

x the number being read
curr_max the largest sum of a run that ends at x
curr_min the smallest sum of a run that ends at x

Start: total, curr_max, curr_min, best and worst are all nums[0] = -2.

nums

-2x

-5

curr_max

-2curr_max

curr_min

-2curr_min

1 / 8

Gotchas1 of 3

The trap
Gotcha 1: Taking total - worst when every number is negative
Mistake
```
return max(best, total - worst)
```
Fix
```
return max(best, total - worst) if best > 0 else best
```
What happens: When every number is negative, the worst plain run is the whole array, so total - worst is 0. That would be an empty run, which is not allowed. The answer is the largest single number, which best already holds.
Example: Maximum Sum Circular Subarray (LC 918): nums = [-3, -2, -3]
Mistake: returns 0Fix: returns -2
Gotcha 2: Removing the best run instead of the worst
Mistake
```
return max(best, total - best) if best > 0 else best
```
Fix
```
return max(best, total - worst) if best > 0 else best
```
What happens: A wrapping run is everything except one plain run in the middle. To make the wrapping run as large as possible, remove the plain run with the smallest sum, the worst one. Removing the best run leaves the smallest piece.
Example: Maximum Sum Circular Subarray (LC 918): nums = [5, -3, 5]
Mistake: returns 7Fix: returns 10
Gotcha 3: Returning only the best plain run
Mistake
```
return best
```
Fix
```
return max(best, total - worst) if best > 0 else best
```
What happens: The best run may wrap around the end. A plain Kadane pass never joins the last numbers to the first ones, so it misses a run such as the two 5s around the -3.
Example: Maximum Sum Circular Subarray (LC 918): nums = [5, -3, 5]
Mistake: returns 7Fix: returns 10

Not this one if…

The array is not circular, so a run never wraps around the end and one Kadane pass is enough, as in Maximum Subarray (LC 53). See Kadane's Algorithm

Deep Dive

Why a wrapping run is the total minus a plain run

In a circular array, the last number is followed by the first number. A run can start near the end and continue at the start. Such a run wraps around.

So the sum of a wrapping run is total minus the sum of a plain run in the middle. To make the wrapping run as large as possible, remove the plain run with the smallest sum. That sum is worst.

Example: for nums = [5, -3, 5], total is 7 and worst is -3. The wrapping run has the sum 7 - (-3) = 10. It is the two 5s that touch at the wrap. A plain pass finds only 7.

Two Kadane passes in one loop

Both passes use the same loop, so the time stays O(N). total adds one more number per step. The space is O(1), with five variables.

The answer is max(best, total - worst). best covers the runs that do not wrap. total - worst covers the runs that wrap.

Trace for nums = [5, -3, 5]: best is 7, worst is -3 and total is 7. The answer is max(7, 10) = 10.

The empty run and the guard

If the removed plain run is the whole array, then total - worst is 0. That is an empty run, and a run must hold at least one number.

This happens when every number is negative. Then worst is the whole array. The correct answer is the largest single number, which is best.

Example: for [-3, -2, -3], total is -8, worst is -8, and the answer is -2. For the single number [-5], the answer is -5.

Checks and a related problem

Example with a longer wrap: nums = [-2, 4, -5, 4, -5, 9, 4] has best = 13, worst = -6 and total = 9. The answer is max(13, 9 + 6) = 15. The run is 9, 4, -2, 4, which wraps around the end.

Maximum Absolute Sum of Any Subarray (LC 1749) uses the same two passes. The answer is max(best, -worst), because the absolute value of the smallest sum can be the largest.

60-Second Pitch

Common Questions

Why does removing the smallest plain run give the best wrapping run?: A wrapping run is the whole circle without one plain run in the middle of the list. Its sum is total minus the sum of that plain run. To make the result as large as possible, remove the plain run with the smallest sum, which is worst.
What does the function return when every number is negative?: The largest single number, which is best. Then worst is the whole array, so total - worst is 0. That would be an empty run, which is not allowed. For [-3, -2, -3], the answer is -2.
What is the time and space complexity?: O(N) time, because one loop runs both Kadane passes and the total. O(1) space, because the function keeps five numbers.
What if the array has only one number?: The loop does not run. best, worst and total all equal nums[0]. If it is positive, total - worst is 0 and best wins. If it is not positive, the guard returns best. For [-5], the answer is -5.
How does Maximum Absolute Sum of Any Subarray (LC 1749) relate to this card?: It uses the same two Kadane passes without the total. The largest absolute sum is the larger of best and -worst. The array is not circular there, so no wrap-around case exists.

SWE Reasoning

Spot it

The question asks for the best sum of one unbroken run of an array.
The array is circular: the last number is followed by the first number.
Plain Kadane's Algorithm fails on a small example such as [5, -3, 5].
The numbers can be negative, so the whole array is not always the best run.
The answer is a sum or a similar value that can be computed as a total minus a middle part.

The invariant, step by step

Before the loop, all five variables start at nums[0]. Only one subarray ends at index 0.
For each x, curr_max and curr_min apply the extend-or-restart rule with max and with min.
best keeps the largest curr_max and worst keeps the smallest curr_min. total adds x.
After the loop, best is the best plain run and worst is the worst plain run.
A run that wraps is total - worst. A run that does not wrap is best.
If best is not positive, total - worst may be an empty run. In that case the function returns best.

Traps

Missing guard. When every number is negative, total - worst is 0, an empty run. For [-3, -2, -3], the result is 0 instead of -2. For [-5], it is 0 instead of -5.
Subtracting best and not worst. The wrapping run needs the smallest middle part removed. See the card's gotcha for [5, -3, 5].
Plain Kadane only. It never joins the end to the start.
Starting at 0. Starting best or worst at 0 allows an empty run. Start all variables at nums[0].

Practice

Canonical LeetCode:Maximum Sum Circular Subarray (LC 918)Maximum Absolute Sum of Any Subarray (LC 1749)

Theory Context•Dynamic Programming

Builds on Kadane's Algorithm, which you haven’t finished yet.

P2MediumBuilt on Linear DP~4 min speedrun

Kadane's Algorithm on a Circular Array (Maximum Sum Circular Subarray)

Built on

Kadane's AlgorithmA run may wrap around the end, and that run is the total minus the worst plain run, so run Kadane a second time with min and keep the total.

The problem

Maximum Sum Circular Subarray (LC 918)(opens leetcode.com)

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.

Example 1

Input:nums = [1,-2,3,-2]

Output:3

The subarray [3] has the largest sum, 3.

Circular Kadane

best plain run, or total - worst plain run ➔ Kadane twice, once with max and once with min ➔ guard the all-negative array

Spot it when: You need the best sum of one unbroken run of a circular array, where the run may wrap around from the end to the start.

Circular Kadane

Python

1	def max_subarray_circular(nums: list[int]) -> int:
2	"""Maximum Sum Circular Subarray: the best plain run, or the total minus the worst plain run.
3	Time: O(N) \| Space: O(1)
4	"""
5	# best, worst: the best and the worst sum of a plain subarray; curr_max, curr_min: the same for one that ends at the current number
6	total = curr_max = curr_min = best = worst = nums[0]
7	for x in nums[1:]:
8	# 1. Run Kadane For The Best And For The Worst:
9	# The same extend-or-restart rule, once with max for the best run and once with min for the worst run.
10	curr_max = max(x, curr_max + x)
11	curr_min = min(x, curr_min + x)
12	best = max(best, curr_max)
13	worst = min(worst, curr_min)
14	total += x
15
16	# 2. Choose The Plain Run Or The Wrapping Run:
17	# A run that wraps around is the total minus a plain run in the middle, so remove the worst plain run.
18	# If every number is negative, the worst plain run is the whole array and the wrapping run would be empty, so keep best.
19	return max(best, total - worst) if best > 0 else best

Invariant: After each x, best and worst are the best and the worst sum of a plain subarray so far, and total is the sum of the numbers seen.

See it run

Circular Kadane, step by step

curr_max -2curr_min -2best -2worst -2total -2

Each column is one index of nums. The rows curr_max and curr_min fill in as the steps run.

x the number being read
curr_max the largest sum of a run that ends at x
curr_min the smallest sum of a run that ends at x

Start: total, curr_max, curr_min, best and worst are all nums[0] = -2.

nums

-2x

-5

curr_max

-2curr_max

curr_min

-2curr_min

1 / 8

Gotchas1 of 3

The trap
Gotcha 1: Taking total - worst when every number is negative
Mistake
```
return max(best, total - worst)
```
Fix
```
return max(best, total - worst) if best > 0 else best
```
What happens: When every number is negative, the worst plain run is the whole array, so total - worst is 0. That would be an empty run, which is not allowed. The answer is the largest single number, which best already holds.
Example: Maximum Sum Circular Subarray (LC 918): nums = [-3, -2, -3]
Mistake: returns 0Fix: returns -2
Gotcha 2: Removing the best run instead of the worst
Mistake
```
return max(best, total - best) if best > 0 else best
```
Fix
```
return max(best, total - worst) if best > 0 else best
```
What happens: A wrapping run is everything except one plain run in the middle. To make the wrapping run as large as possible, remove the plain run with the smallest sum, the worst one. Removing the best run leaves the smallest piece.
Example: Maximum Sum Circular Subarray (LC 918): nums = [5, -3, 5]
Mistake: returns 7Fix: returns 10
Gotcha 3: Returning only the best plain run
Mistake
```
return best
```
Fix
```
return max(best, total - worst) if best > 0 else best
```
What happens: The best run may wrap around the end. A plain Kadane pass never joins the last numbers to the first ones, so it misses a run such as the two 5s around the -3.
Example: Maximum Sum Circular Subarray (LC 918): nums = [5, -3, 5]
Mistake: returns 7Fix: returns 10

Not this one if…

The array is not circular, so a run never wraps around the end and one Kadane pass is enough, as in Maximum Subarray (LC 53). See Kadane's Algorithm

Deep Dive

Why a wrapping run is the total minus a plain run

In a circular array, the last number is followed by the first number. A run can start near the end and continue at the start. Such a run wraps around.

So the sum of a wrapping run is total minus the sum of a plain run in the middle. To make the wrapping run as large as possible, remove the plain run with the smallest sum. That sum is worst.

Example: for nums = [5, -3, 5], total is 7 and worst is -3. The wrapping run has the sum 7 - (-3) = 10. It is the two 5s that touch at the wrap. A plain pass finds only 7.

Two Kadane passes in one loop

Both passes use the same loop, so the time stays O(N). total adds one more number per step. The space is O(1), with five variables.

The answer is max(best, total - worst). best covers the runs that do not wrap. total - worst covers the runs that wrap.

Trace for nums = [5, -3, 5]: best is 7, worst is -3 and total is 7. The answer is max(7, 10) = 10.

The empty run and the guard

If the removed plain run is the whole array, then total - worst is 0. That is an empty run, and a run must hold at least one number.

This happens when every number is negative. Then worst is the whole array. The correct answer is the largest single number, which is best.

Example: for [-3, -2, -3], total is -8, worst is -8, and the answer is -2. For the single number [-5], the answer is -5.

Checks and a related problem

Example with a longer wrap: nums = [-2, 4, -5, 4, -5, 9, 4] has best = 13, worst = -6 and total = 9. The answer is max(13, 9 + 6) = 15. The run is 9, 4, -2, 4, which wraps around the end.

Maximum Absolute Sum of Any Subarray (LC 1749) uses the same two passes. The answer is max(best, -worst), because the absolute value of the smallest sum can be the largest.

60-Second Pitch

Common Questions

Why does removing the smallest plain run give the best wrapping run?: A wrapping run is the whole circle without one plain run in the middle of the list. Its sum is total minus the sum of that plain run. To make the result as large as possible, remove the plain run with the smallest sum, which is worst.
What does the function return when every number is negative?: The largest single number, which is best. Then worst is the whole array, so total - worst is 0. That would be an empty run, which is not allowed. For [-3, -2, -3], the answer is -2.
What is the time and space complexity?: O(N) time, because one loop runs both Kadane passes and the total. O(1) space, because the function keeps five numbers.
What if the array has only one number?: The loop does not run. best, worst and total all equal nums[0]. If it is positive, total - worst is 0 and best wins. If it is not positive, the guard returns best. For [-5], the answer is -5.
How does Maximum Absolute Sum of Any Subarray (LC 1749) relate to this card?: It uses the same two Kadane passes without the total. The largest absolute sum is the larger of best and -worst. The array is not circular there, so no wrap-around case exists.

SWE Reasoning

Spot it

The question asks for the best sum of one unbroken run of an array.
The array is circular: the last number is followed by the first number.
Plain Kadane's Algorithm fails on a small example such as [5, -3, 5].
The numbers can be negative, so the whole array is not always the best run.
The answer is a sum or a similar value that can be computed as a total minus a middle part.

The invariant, step by step

Before the loop, all five variables start at nums[0]. Only one subarray ends at index 0.
For each x, curr_max and curr_min apply the extend-or-restart rule with max and with min.
best keeps the largest curr_max and worst keeps the smallest curr_min. total adds x.
After the loop, best is the best plain run and worst is the worst plain run.
A run that wraps is total - worst. A run that does not wrap is best.
If best is not positive, total - worst may be an empty run. In that case the function returns best.

Traps

Missing guard. When every number is negative, total - worst is 0, an empty run. For [-3, -2, -3], the result is 0 instead of -2. For [-5], it is 0 instead of -5.
Subtracting best and not worst. The wrapping run needs the smallest middle part removed. See the card's gotcha for [5, -3, 5].
Plain Kadane only. It never joins the end to the start.
Starting at 0. Starting best or worst at 0 allows an empty run. Start all variables at nums[0].

Practice

Canonical LeetCode:Maximum Sum Circular Subarray (LC 918)Maximum Absolute Sum of Any Subarray (LC 1749)

Theory Context•Dynamic Programming

Builds on Kadane's Algorithm, which you haven’t finished yet.

P2MediumBuilt on Linear DP~4 min speedrun

Kadane's Algorithm on a Circular Array (Maximum Sum Circular Subarray)

Built on

Kadane's AlgorithmA run may wrap around the end, and that run is the total minus the worst plain run, so run Kadane a second time with min and keep the total.

The problem

Maximum Sum Circular Subarray (LC 918)(opens leetcode.com)

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.

Example 1

Input:nums = [1,-2,3,-2]

Output:3

The subarray [3] has the largest sum, 3.

Circular Kadane

best plain run, or total - worst plain run ➔ Kadane twice, once with max and once with min ➔ guard the all-negative array

Spot it when: You need the best sum of one unbroken run of a circular array, where the run may wrap around from the end to the start.

Circular Kadane

Python

1	def max_subarray_circular(nums: list[int]) -> int:
2	"""Maximum Sum Circular Subarray: the best plain run, or the total minus the worst plain run.
3	Time: O(N) \| Space: O(1)
4	"""
5	# best, worst: the best and the worst sum of a plain subarray; curr_max, curr_min: the same for one that ends at the current number
6	total = curr_max = curr_min = best = worst = nums[0]
7	for x in nums[1:]:
8	# 1. Run Kadane For The Best And For The Worst:
9	# The same extend-or-restart rule, once with max for the best run and once with min for the worst run.
10	curr_max = max(x, curr_max + x)
11	curr_min = min(x, curr_min + x)
12	best = max(best, curr_max)
13	worst = min(worst, curr_min)
14	total += x
15
16	# 2. Choose The Plain Run Or The Wrapping Run:
17	# A run that wraps around is the total minus a plain run in the middle, so remove the worst plain run.
18	# If every number is negative, the worst plain run is the whole array and the wrapping run would be empty, so keep best.
19	return max(best, total - worst) if best > 0 else best

Invariant: After each x, best and worst are the best and the worst sum of a plain subarray so far, and total is the sum of the numbers seen.

See it run

Circular Kadane, step by step

curr_max -2curr_min -2best -2worst -2total -2

Each column is one index of nums. The rows curr_max and curr_min fill in as the steps run.

x the number being read
curr_max the largest sum of a run that ends at x
curr_min the smallest sum of a run that ends at x

Start: total, curr_max, curr_min, best and worst are all nums[0] = -2.

nums

-2x

-5

curr_max

-2curr_max

curr_min

-2curr_min

1 / 8

Gotchas1 of 3

The trap
Gotcha 1: Taking total - worst when every number is negative
Mistake
```
return max(best, total - worst)
```
Fix
```
return max(best, total - worst) if best > 0 else best
```
What happens: When every number is negative, the worst plain run is the whole array, so total - worst is 0. That would be an empty run, which is not allowed. The answer is the largest single number, which best already holds.
Example: Maximum Sum Circular Subarray (LC 918): nums = [-3, -2, -3]
Mistake: returns 0Fix: returns -2
Gotcha 2: Removing the best run instead of the worst
Mistake
```
return max(best, total - best) if best > 0 else best
```
Fix
```
return max(best, total - worst) if best > 0 else best
```
What happens: A wrapping run is everything except one plain run in the middle. To make the wrapping run as large as possible, remove the plain run with the smallest sum, the worst one. Removing the best run leaves the smallest piece.
Example: Maximum Sum Circular Subarray (LC 918): nums = [5, -3, 5]
Mistake: returns 7Fix: returns 10
Gotcha 3: Returning only the best plain run
Mistake
```
return best
```
Fix
```
return max(best, total - worst) if best > 0 else best
```
What happens: The best run may wrap around the end. A plain Kadane pass never joins the last numbers to the first ones, so it misses a run such as the two 5s around the -3.
Example: Maximum Sum Circular Subarray (LC 918): nums = [5, -3, 5]
Mistake: returns 7Fix: returns 10

Not this one if…

The array is not circular, so a run never wraps around the end and one Kadane pass is enough, as in Maximum Subarray (LC 53). See Kadane's Algorithm

Deep Dive

Why a wrapping run is the total minus a plain run

In a circular array, the last number is followed by the first number. A run can start near the end and continue at the start. Such a run wraps around.

So the sum of a wrapping run is total minus the sum of a plain run in the middle. To make the wrapping run as large as possible, remove the plain run with the smallest sum. That sum is worst.

Example: for nums = [5, -3, 5], total is 7 and worst is -3. The wrapping run has the sum 7 - (-3) = 10. It is the two 5s that touch at the wrap. A plain pass finds only 7.

Two Kadane passes in one loop

Both passes use the same loop, so the time stays O(N). total adds one more number per step. The space is O(1), with five variables.

The answer is max(best, total - worst). best covers the runs that do not wrap. total - worst covers the runs that wrap.

Trace for nums = [5, -3, 5]: best is 7, worst is -3 and total is 7. The answer is max(7, 10) = 10.

The empty run and the guard

If the removed plain run is the whole array, then total - worst is 0. That is an empty run, and a run must hold at least one number.

This happens when every number is negative. Then worst is the whole array. The correct answer is the largest single number, which is best.

Example: for [-3, -2, -3], total is -8, worst is -8, and the answer is -2. For the single number [-5], the answer is -5.

Checks and a related problem

Example with a longer wrap: nums = [-2, 4, -5, 4, -5, 9, 4] has best = 13, worst = -6 and total = 9. The answer is max(13, 9 + 6) = 15. The run is 9, 4, -2, 4, which wraps around the end.

Maximum Absolute Sum of Any Subarray (LC 1749) uses the same two passes. The answer is max(best, -worst), because the absolute value of the smallest sum can be the largest.

60-Second Pitch

Common Questions

Why does removing the smallest plain run give the best wrapping run?: A wrapping run is the whole circle without one plain run in the middle of the list. Its sum is total minus the sum of that plain run. To make the result as large as possible, remove the plain run with the smallest sum, which is worst.
What does the function return when every number is negative?: The largest single number, which is best. Then worst is the whole array, so total - worst is 0. That would be an empty run, which is not allowed. For [-3, -2, -3], the answer is -2.
What is the time and space complexity?: O(N) time, because one loop runs both Kadane passes and the total. O(1) space, because the function keeps five numbers.
What if the array has only one number?: The loop does not run. best, worst and total all equal nums[0]. If it is positive, total - worst is 0 and best wins. If it is not positive, the guard returns best. For [-5], the answer is -5.
How does Maximum Absolute Sum of Any Subarray (LC 1749) relate to this card?: It uses the same two Kadane passes without the total. The largest absolute sum is the larger of best and -worst. The array is not circular there, so no wrap-around case exists.

SWE Reasoning

Spot it

The question asks for the best sum of one unbroken run of an array.
The array is circular: the last number is followed by the first number.
Plain Kadane's Algorithm fails on a small example such as [5, -3, 5].
The numbers can be negative, so the whole array is not always the best run.
The answer is a sum or a similar value that can be computed as a total minus a middle part.

The invariant, step by step

Before the loop, all five variables start at nums[0]. Only one subarray ends at index 0.
For each x, curr_max and curr_min apply the extend-or-restart rule with max and with min.
best keeps the largest curr_max and worst keeps the smallest curr_min. total adds x.
After the loop, best is the best plain run and worst is the worst plain run.
A run that wraps is total - worst. A run that does not wrap is best.
If best is not positive, total - worst may be an empty run. In that case the function returns best.

Traps

Missing guard. When every number is negative, total - worst is 0, an empty run. For [-3, -2, -3], the result is 0 instead of -2. For [-5], it is 0 instead of -5.
Subtracting best and not worst. The wrapping run needs the smallest middle part removed. See the card's gotcha for [5, -3, 5].
Plain Kadane only. It never joins the end to the start.
Starting at 0. Starting best or worst at 0 allows an empty run. Start all variables at nums[0].

Practice

Canonical LeetCode:Maximum Sum Circular Subarray (LC 918)Maximum Absolute Sum of Any Subarray (LC 1749)