Builds on Kadane's Algorithm, which you haven’t finished yet.
Kadane's Algorithm for the Best and the Worst Run (Maximum Absolute Sum of Any Subarray)
max and with min, let each run restart at 0, and take the larger of curr_max and -curr_min.The input is a list of integers nums. Take any run of neighbouring entries (a subarray), add them up, and then ignore the sign of the total: that value is the run's absolute sum. A total of -8 gives 8.
Find the largest absolute sum over all runs. The empty run is allowed, so the answer is never below 0.
[2, 3] has sum 5, so its absolute sum is 5. No subarray has a larger absolute sum.Max Absolute Subarray Sum
curr_max and curr_min = best and worst sum ending here ➔ each restarts at 0 ➔ keep the larger of curr_max and -curr_min| 1 | def max_absolute_sum(nums: list[int]) -> int: |
| 2 | """Maximum Absolute Sum of Any Subarray: the best run and the worst run, each allowed to be empty. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | # curr_max, curr_min: the best and the worst sum of a subarray ending at the current number (0 for an empty one); best: the largest absolute value seen |
| 6 | curr_max = curr_min = best = 0 |
| 7 | for x in nums: |
| 8 | # 1. Run Kadane For The Best And For The Worst: |
| 9 | # curr_max and curr_min restart at 0 when they would get worse, because the empty subarray (sum 0) is allowed. |
| 10 | curr_max = max(0, curr_max + x) |
| 11 | curr_min = min(0, curr_min + x) |
| 12 | |
| 13 | # 2. Track The Largest Absolute Value: |
| 14 | # The best run counts as it is, and the worst run counts as its negative. |
| 15 | best = max(best, curr_max, -curr_min) |
| 16 | |
| 17 | return best |
x, curr_max and curr_min are the best and the worst sum of a subarray that ends at x (0 for the empty one), and best is the largest of curr_max and -curr_min seen.The absolute sum of a run is large when its sum is very positive or very negative, so run Kadane's Algorithm twice: curr_max = max(0, curr_max + x) for the best run and curr_min = min(0, curr_min + x) for the worst run. The empty run has sum 0 and is allowed, so a run that gets worse restarts at 0. best = max(best, curr_max, -curr_min) measures both by absolute value. The trap is the sign: curr_min is never positive, so it must enter best as -curr_min.
See it run
Maximum Absolute Sum of Any Subarray, step by step
curr_max 0curr_min 0best 0
Each column is one index of nums. The rows curr_max and curr_min fill in as the steps run.
xthe number being readcurr_maxthe largest run sum that ends at x (never below 0)curr_minthe smallest run sum that ends at x (never above 0)
Start: curr_max = curr_min = best = 0. An empty run has the sum 0.
Gotcha 1 of 3
- The trap
Gotcha 1: Tracking only the best run
Mistakebest = max(best, curr_max)Fixbest = max(best, curr_max, -curr_min)What happens: The absolute sum is large for a very negative sum too. With only the best run, a stretch of falling numbers is never counted, so the answer is the largest positive sum instead of the largest absolute value of a sum.
Example: Maximum Absolute Sum of Any Subarray (LC 1749): nums = [2, -5, 1, -4, 3, -2]Mistake: returns 3Fix: returns 8
- The target is the largest sum, not the largest absolute value of a sum, so only the best run is needed and it restarts at
x, as in Maximum Subarray (LC 53). See Kadane's Algorithm
Deep Dive
Why two Kadane runs cover an absolute value
The absolute value of a sum is large in two cases. The sum is a large positive number, or the sum is a large negative number. The largest absolute sum is the larger of the two cases: the largest sum of any subarray, and the negative of the smallest sum of any subarray.
Each case is one Kadane run. curr_max follows the best sum that ends at the current number, and curr_min follows the worst sum that ends there. The two runs never read each other, so they can share one loop.
best = max(best, curr_max, -curr_min) compares both in the same units. curr_min is never positive, so its absolute value is -curr_min.
Why each run restarts at 0
This card allows the empty subarray, whose sum is 0. So a run that stops helping can restart at 0 and not at x. That is why the update is max(0, curr_max + x) and min(0, curr_min + x).
This does not change the answer. If the array has a number that is not 0, the largest absolute sum is at least the absolute value of that number, so it is greater than 0. If every number is 0, the answer is 0 in both versions. For [0], the answer is 0.
It also makes the starting values simple: curr_max = curr_min = best = 0, and the loop covers every number.
Trace and the prefix-sum view
Trace for nums = [2, -5, 1, -4, 3, -2], as x, curr_max, curr_min, best:
2, 2, 0, 2.-5, 0, -5, 5.1, 1, -4, 5.-4, 0, -8, 8.3, 3, -5, 8.-2, 1, -7, 8.
The answer is 8, from the run [-5, 1, -4], whose sum is -8.
There is a second view. Let P[k] be the sum of the first k numbers, with P[0] = 0. The sum of the numbers from index i to index j - 1 is P[j] - P[i]. Its absolute value is the distance between two prefix sums, and the order of the two does not matter.
So the largest absolute sum is the largest prefix sum minus the smallest prefix sum. Here P is [0, 2, -3, -2, -6, -3, -5]. The largest is 2 and the smallest is -6, so the answer is 8. This method needs one pass and two variables, and it agrees with the Kadane method on thousands of random arrays.
The cost and a related problem
There are N states. Each does two max or min calls and one comparison. The time is O(N) and the space is O(1).
The brute force tries every start and end: N * (N + 1) / 2 subarrays. For the six numbers above, that is 21.
Maximum Sum Circular Subarray (LC 918) also runs Kadane's Algorithm with max and with min in one loop. The Circular Kadane card explains how it combines the two results with the total of the array.
60-Second Pitch
"The absolute sum is large when the sum is very positive or very negative. So I run Kadane's Algorithm twice in one loop: curr_max for the best sum ending here, and curr_min for the worst sum ending here. The empty subarray is allowed, so each run restarts at 0. I keep best as the largest of curr_max and -curr_min. The time is O(N) and the space is O(1). An equivalent method is the largest prefix sum minus the smallest prefix sum."
Common Questions
- Why is the answer the largest prefix sum minus the smallest prefix sum?
A subarray sum is the difference between two prefix sums,
P[j] - P[i]. The absolute value of a difference does not depend on the order of the two values. So the largest possible absolute sum is the largest prefix sum minus the smallest one, withP[0] = 0included. For[2, -5, 1, -4, 3, -2], it is 2 - (-6) = 8.- Why can each run restart at 0 and not at
x? The empty subarray, with sum 0, is allowed. A run that has become negative (for the best run) can start again from nothing, and the result is never worse than 0. This does not change the answer, because any non-zero number already gives an absolute sum above 0.
- What is the time and space complexity?
O(N)time, because one loop updates both runs.O(1)space, because onlycurr_max,curr_minandbestexist.- What is the answer for an array of one number, or an array of zeros?
For one number
x, the answer isabs(x). For[-7], it is 7. For an array of zeros, it is 0.- How does this differ from Maximum Sum Circular Subarray (LC 918)?
Both run Kadane's Algorithm with
maxand withmin. Here the array is not circular, and the answer is the larger ofbestand-worst. In the circular problem, the answer is the larger ofbestandtotal - worst, with a guard for arrays of negative numbers.
SWE Reasoning
Spot it
- The question asks for the largest absolute value of the sum of one unbroken run.
- A run with a very negative sum counts as much as a run with a very positive sum.
- The empty subarray is allowed, with sum 0.
- Plain Kadane's Algorithm finds only the positive side.
- Prefix sums are an equivalent view: the answer is the largest minus the smallest.
The invariant, step by step
- Before the loop,
curr_max,curr_minandbestare all 0. The empty subarray has sum 0. - For each
x,curr_max = max(0, curr_max + x)is the best sum of a subarray that ends atx, or 0 for the empty one. curr_min = min(0, curr_min + x)is the worst sum of a subarray that ends atx, or 0 for the empty one.best = max(best, curr_max, -curr_min)keeps the largest absolute value seen.- Every subarray ends at some index, so both the best and the worst sums are covered.
- After the loop,
bestis the answer.
Traps
- Tracking only the best run. A strongly negative run is never counted. See the card's gotcha for
[2, -5, 1, -4, 3, -2]. - Missing minus sign.
curr_minis never positive, somax(best, curr_max, curr_min)ignores it. See the card's gotcha for[-5, 1, -4]. - One accumulator with
abs.curr = abs(curr + x)mixes both runs. For[3, -5], the result is 3 instead of 5. - Returning
curr_max - curr_min. The two runs may end at different indices, and they may overlap. Their difference is not a subarray sum. - Wrong problem. If the empty subarray is not allowed, or the target is the best sum and not an absolute value, use Kadane's Algorithm from its own card.
Practice
Builds on Kadane's Algorithm, which you haven’t finished yet.
Kadane's Algorithm for the Best and the Worst Run (Maximum Absolute Sum of Any Subarray)
max and with min, let each run restart at 0, and take the larger of curr_max and -curr_min.The input is a list of integers nums. Take any run of neighbouring entries (a subarray), add them up, and then ignore the sign of the total: that value is the run's absolute sum. A total of -8 gives 8.
Find the largest absolute sum over all runs. The empty run is allowed, so the answer is never below 0.
[2, 3] has sum 5, so its absolute sum is 5. No subarray has a larger absolute sum.Max Absolute Subarray Sum
curr_max and curr_min = best and worst sum ending here ➔ each restarts at 0 ➔ keep the larger of curr_max and -curr_min| 1 | def max_absolute_sum(nums: list[int]) -> int: |
| 2 | """Maximum Absolute Sum of Any Subarray: the best run and the worst run, each allowed to be empty. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | # curr_max, curr_min: the best and the worst sum of a subarray ending at the current number (0 for an empty one); best: the largest absolute value seen |
| 6 | curr_max = curr_min = best = 0 |
| 7 | for x in nums: |
| 8 | # 1. Run Kadane For The Best And For The Worst: |
| 9 | # curr_max and curr_min restart at 0 when they would get worse, because the empty subarray (sum 0) is allowed. |
| 10 | curr_max = max(0, curr_max + x) |
| 11 | curr_min = min(0, curr_min + x) |
| 12 | |
| 13 | # 2. Track The Largest Absolute Value: |
| 14 | # The best run counts as it is, and the worst run counts as its negative. |
| 15 | best = max(best, curr_max, -curr_min) |
| 16 | |
| 17 | return best |
x, curr_max and curr_min are the best and the worst sum of a subarray that ends at x (0 for the empty one), and best is the largest of curr_max and -curr_min seen.The absolute sum of a run is large when its sum is very positive or very negative, so run Kadane's Algorithm twice: curr_max = max(0, curr_max + x) for the best run and curr_min = min(0, curr_min + x) for the worst run. The empty run has sum 0 and is allowed, so a run that gets worse restarts at 0. best = max(best, curr_max, -curr_min) measures both by absolute value. The trap is the sign: curr_min is never positive, so it must enter best as -curr_min.
See it run
Maximum Absolute Sum of Any Subarray, step by step
curr_max 0curr_min 0best 0
Each column is one index of nums. The rows curr_max and curr_min fill in as the steps run.
xthe number being readcurr_maxthe largest run sum that ends at x (never below 0)curr_minthe smallest run sum that ends at x (never above 0)
Start: curr_max = curr_min = best = 0. An empty run has the sum 0.
Gotcha 1 of 3
- The trap
Gotcha 1: Tracking only the best run
Mistakebest = max(best, curr_max)Fixbest = max(best, curr_max, -curr_min)What happens: The absolute sum is large for a very negative sum too. With only the best run, a stretch of falling numbers is never counted, so the answer is the largest positive sum instead of the largest absolute value of a sum.
Example: Maximum Absolute Sum of Any Subarray (LC 1749): nums = [2, -5, 1, -4, 3, -2]Mistake: returns 3Fix: returns 8
- The target is the largest sum, not the largest absolute value of a sum, so only the best run is needed and it restarts at
x, as in Maximum Subarray (LC 53). See Kadane's Algorithm
Deep Dive
Why two Kadane runs cover an absolute value
The absolute value of a sum is large in two cases. The sum is a large positive number, or the sum is a large negative number. The largest absolute sum is the larger of the two cases: the largest sum of any subarray, and the negative of the smallest sum of any subarray.
Each case is one Kadane run. curr_max follows the best sum that ends at the current number, and curr_min follows the worst sum that ends there. The two runs never read each other, so they can share one loop.
best = max(best, curr_max, -curr_min) compares both in the same units. curr_min is never positive, so its absolute value is -curr_min.
Why each run restarts at 0
This card allows the empty subarray, whose sum is 0. So a run that stops helping can restart at 0 and not at x. That is why the update is max(0, curr_max + x) and min(0, curr_min + x).
This does not change the answer. If the array has a number that is not 0, the largest absolute sum is at least the absolute value of that number, so it is greater than 0. If every number is 0, the answer is 0 in both versions. For [0], the answer is 0.
It also makes the starting values simple: curr_max = curr_min = best = 0, and the loop covers every number.
Trace and the prefix-sum view
Trace for nums = [2, -5, 1, -4, 3, -2], as x, curr_max, curr_min, best:
2, 2, 0, 2.-5, 0, -5, 5.1, 1, -4, 5.-4, 0, -8, 8.3, 3, -5, 8.-2, 1, -7, 8.
The answer is 8, from the run [-5, 1, -4], whose sum is -8.
There is a second view. Let P[k] be the sum of the first k numbers, with P[0] = 0. The sum of the numbers from index i to index j - 1 is P[j] - P[i]. Its absolute value is the distance between two prefix sums, and the order of the two does not matter.
So the largest absolute sum is the largest prefix sum minus the smallest prefix sum. Here P is [0, 2, -3, -2, -6, -3, -5]. The largest is 2 and the smallest is -6, so the answer is 8. This method needs one pass and two variables, and it agrees with the Kadane method on thousands of random arrays.
The cost and a related problem
There are N states. Each does two max or min calls and one comparison. The time is O(N) and the space is O(1).
The brute force tries every start and end: N * (N + 1) / 2 subarrays. For the six numbers above, that is 21.
Maximum Sum Circular Subarray (LC 918) also runs Kadane's Algorithm with max and with min in one loop. The Circular Kadane card explains how it combines the two results with the total of the array.
60-Second Pitch
"The absolute sum is large when the sum is very positive or very negative. So I run Kadane's Algorithm twice in one loop: curr_max for the best sum ending here, and curr_min for the worst sum ending here. The empty subarray is allowed, so each run restarts at 0. I keep best as the largest of curr_max and -curr_min. The time is O(N) and the space is O(1). An equivalent method is the largest prefix sum minus the smallest prefix sum."
Common Questions
- Why is the answer the largest prefix sum minus the smallest prefix sum?
A subarray sum is the difference between two prefix sums,
P[j] - P[i]. The absolute value of a difference does not depend on the order of the two values. So the largest possible absolute sum is the largest prefix sum minus the smallest one, withP[0] = 0included. For[2, -5, 1, -4, 3, -2], it is 2 - (-6) = 8.- Why can each run restart at 0 and not at
x? The empty subarray, with sum 0, is allowed. A run that has become negative (for the best run) can start again from nothing, and the result is never worse than 0. This does not change the answer, because any non-zero number already gives an absolute sum above 0.
- What is the time and space complexity?
O(N)time, because one loop updates both runs.O(1)space, because onlycurr_max,curr_minandbestexist.- What is the answer for an array of one number, or an array of zeros?
For one number
x, the answer isabs(x). For[-7], it is 7. For an array of zeros, it is 0.- How does this differ from Maximum Sum Circular Subarray (LC 918)?
Both run Kadane's Algorithm with
maxand withmin. Here the array is not circular, and the answer is the larger ofbestand-worst. In the circular problem, the answer is the larger ofbestandtotal - worst, with a guard for arrays of negative numbers.
SWE Reasoning
Spot it
- The question asks for the largest absolute value of the sum of one unbroken run.
- A run with a very negative sum counts as much as a run with a very positive sum.
- The empty subarray is allowed, with sum 0.
- Plain Kadane's Algorithm finds only the positive side.
- Prefix sums are an equivalent view: the answer is the largest minus the smallest.
The invariant, step by step
- Before the loop,
curr_max,curr_minandbestare all 0. The empty subarray has sum 0. - For each
x,curr_max = max(0, curr_max + x)is the best sum of a subarray that ends atx, or 0 for the empty one. curr_min = min(0, curr_min + x)is the worst sum of a subarray that ends atx, or 0 for the empty one.best = max(best, curr_max, -curr_min)keeps the largest absolute value seen.- Every subarray ends at some index, so both the best and the worst sums are covered.
- After the loop,
bestis the answer.
Traps
- Tracking only the best run. A strongly negative run is never counted. See the card's gotcha for
[2, -5, 1, -4, 3, -2]. - Missing minus sign.
curr_minis never positive, somax(best, curr_max, curr_min)ignores it. See the card's gotcha for[-5, 1, -4]. - One accumulator with
abs.curr = abs(curr + x)mixes both runs. For[3, -5], the result is 3 instead of 5. - Returning
curr_max - curr_min. The two runs may end at different indices, and they may overlap. Their difference is not a subarray sum. - Wrong problem. If the empty subarray is not allowed, or the target is the best sum and not an absolute value, use Kadane's Algorithm from its own card.