Maximum Absolute Sum of Any Subarray (LeetCode 1749)
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.
Worked Examples
nums = [1,-3,2,3,-4]5[2, 3] has sum 5, so its absolute sum is 5. No subarray has a larger absolute sum.nums = [2,-5,1,-4,3,-2]8[-5, 1, -4] has sum -8, so its absolute sum is 8.⚖️Formal Constraints & Bounds
1 <= nums.length <= 105-104 <= nums[i] <= 104
Core Insight
The absolute sum is the larger of the best sum and the negative of the worst sum, so run Kadane's Algorithm once with max and once with min, let each run restart at 0 because the empty subarray is allowed, and measure both by absolute value.
Real-World Scenario & Production Applications
A balance that goes up and down over time, such as an account: the largest swing in either direction over a stretch of days is the largest absolute sum of a run of daily changes.
Step-by-Step Execution Trace Table
Trace of Example 1: nums = [1, -3, 2, 3, -4]. curr_max, curr_min and best start at 0.
x | curr_max | curr_min | best |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| -3 | 0 | -2 | 2 |
| 2 | 2 | 0 | 2 |
| 3 | 5 | 0 | 5 |
| -4 | 1 | -4 | 5 |
At x = -3, the best run restarts at 0 because 1 - 3 is below 0, and the worst run is -2, so -curr_min = 2.
| 1 | curr_max = curr_min = best = 0 |
| 2 | for x in nums: |
| 3 | curr_max = max(0, curr_max + x); curr_min = min(0, curr_min + x) |
| 4 | best = max(best, curr_max, -curr_min) |
| 5 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The absolute sum of a subarray is the size of its sum, whether the sum is positive or negative. So the answer is the larger of two numbers: the best sum of any subarray, and the worst sum of any subarray with its sign removed. Kadane's Algorithm finds the best sum. Run it a second time with min to find the worst.
➗ What Is Added To Kadane
Kadane's Algorithm is run twice, once with max and once with min, and the answer takes the larger of curr_max and -curr_min. The empty subarray is allowed here, so a run below 0 restarts at 0.
🔑 The Key Idea in the Code
Because the empty subarray has absolute sum 0, max(0, curr_max + x) is safe: a dropped run costs nothing. The all-negative array needs no special case, since the worst run is then the answer.
Dropping a run at 0 when the subarray must be non-empty:
max(0, curr_max + x)is correct for the absolute sum, where the empty subarray is allowed. For a non-empty subarray, usemax(x, curr_max + x).Tracking only the best run: the worst run counts too, as its negative.
[2, -5, 1, -4, 3, -2]returns 4 instead of 8 if only the best run is kept.Forgetting the minus sign on the worst run:
best = max(best, curr_max, curr_min)never uses a negative run, becausecurr_minis not positive. Use-curr_min.Comparing the two runs in one variable: the best run and the worst run are separate accumulators, because each one restarts at a different sign.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The largest absolute sum of any subarray": a best value over contiguous runs, which points to Kadane's Algorithm. The absolute value means a very negative sum counts too, so one run is not enough.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
curr_max is the best and curr_min is the worst sum of a subarray ending here, where the empty subarray (sum 0) is allowed. Each run restarts at 0 when it would get worse. best is the largest of curr_max and -curr_min.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Using the non-empty rule
max(x, curr_max + x)withbeststarting at 0 works too, but mixing the two rules does not.
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. The absolute sum of a subarray is the larger of its sum and the negative of its sum, so the answer is the larger of the best subarray sum and the negative of the worst subarray sum. I keep curr max and curr min, the best and the worst sum of a subarray ending at the current number. The empty subarray is allowed and has sum zero, so each one restarts at zero when it would get worse. I keep the largest of curr max and minus curr min. That is one pass, order N time and order 1 space. An equivalent view: the answer is the largest prefix sum minus the smallest prefix sum.
Complexity & Mathematical Proof
O(N)
Look at the loop. for x in nums visits each number once. Each visit does two max or min steps and one global update, which is constant work. That is N steps, so time is O(N).
O(1)
The code keeps three variables, curr_max, curr_min and best, whatever the length of nums is. There is no table and no recursion, so space is O(1).
Derivation Progression
for x in nums visits each number once.
3 = O(1)
One max step, one min step and one global update.
3N = O(N)
Numbers times a constant amount of work.
Variable Definitions
Length of nums
Best sum of a subarray ending at the current number, restarting at 0
Worst sum of a subarray ending at the current number, restarting at 0
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables curr_max, curr_min and best
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: "the largest absolute sum of any subarray". The absolute value means the best run and the worst run both count, so this is Kadane's Algorithm run twice: once with max and once, mirrored, with min.
and , so a sum is at most , which fits in 32 bits. A loop over all pairs is steps; one pass is .
The empty subarray is allowed here, so max(0, curr_max + x) is correct. Using the non-empty rule max(x, curr_max + x) also works, but then best must start at 0, not at nums[0]. Forgetting -curr_min and tracking only curr_max misses arrays whose largest absolute sum is negative.
Maximum Absolute Sum of Any Subarray (LeetCode 1749)
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.
Worked Examples
nums = [1,-3,2,3,-4]5[2, 3] has sum 5, so its absolute sum is 5. No subarray has a larger absolute sum.nums = [2,-5,1,-4,3,-2]8[-5, 1, -4] has sum -8, so its absolute sum is 8.⚖️Formal Constraints & Bounds
1 <= nums.length <= 105-104 <= nums[i] <= 104
Core Insight
The absolute sum is the larger of the best sum and the negative of the worst sum, so run Kadane's Algorithm once with max and once with min, let each run restart at 0 because the empty subarray is allowed, and measure both by absolute value.
Real-World Scenario & Production Applications
A balance that goes up and down over time, such as an account: the largest swing in either direction over a stretch of days is the largest absolute sum of a run of daily changes.
Step-by-Step Execution Trace Table
Trace of Example 1: nums = [1, -3, 2, 3, -4]. curr_max, curr_min and best start at 0.
x | curr_max | curr_min | best |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| -3 | 0 | -2 | 2 |
| 2 | 2 | 0 | 2 |
| 3 | 5 | 0 | 5 |
| -4 | 1 | -4 | 5 |
At x = -3, the best run restarts at 0 because 1 - 3 is below 0, and the worst run is -2, so -curr_min = 2.
| 1 | curr_max = curr_min = best = 0 |
| 2 | for x in nums: |
| 3 | curr_max = max(0, curr_max + x); curr_min = min(0, curr_min + x) |
| 4 | best = max(best, curr_max, -curr_min) |
| 5 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The absolute sum of a subarray is the size of its sum, whether the sum is positive or negative. So the answer is the larger of two numbers: the best sum of any subarray, and the worst sum of any subarray with its sign removed. Kadane's Algorithm finds the best sum. Run it a second time with min to find the worst.
➗ What Is Added To Kadane
Kadane's Algorithm is run twice, once with max and once with min, and the answer takes the larger of curr_max and -curr_min. The empty subarray is allowed here, so a run below 0 restarts at 0.
🔑 The Key Idea in the Code
Because the empty subarray has absolute sum 0, max(0, curr_max + x) is safe: a dropped run costs nothing. The all-negative array needs no special case, since the worst run is then the answer.
Dropping a run at 0 when the subarray must be non-empty:
max(0, curr_max + x)is correct for the absolute sum, where the empty subarray is allowed. For a non-empty subarray, usemax(x, curr_max + x).Tracking only the best run: the worst run counts too, as its negative.
[2, -5, 1, -4, 3, -2]returns 4 instead of 8 if only the best run is kept.Forgetting the minus sign on the worst run:
best = max(best, curr_max, curr_min)never uses a negative run, becausecurr_minis not positive. Use-curr_min.Comparing the two runs in one variable: the best run and the worst run are separate accumulators, because each one restarts at a different sign.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The largest absolute sum of any subarray": a best value over contiguous runs, which points to Kadane's Algorithm. The absolute value means a very negative sum counts too, so one run is not enough.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
curr_max is the best and curr_min is the worst sum of a subarray ending here, where the empty subarray (sum 0) is allowed. Each run restarts at 0 when it would get worse. best is the largest of curr_max and -curr_min.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Using the non-empty rule
max(x, curr_max + x)withbeststarting at 0 works too, but mixing the two rules does not.
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. The absolute sum of a subarray is the larger of its sum and the negative of its sum, so the answer is the larger of the best subarray sum and the negative of the worst subarray sum. I keep curr max and curr min, the best and the worst sum of a subarray ending at the current number. The empty subarray is allowed and has sum zero, so each one restarts at zero when it would get worse. I keep the largest of curr max and minus curr min. That is one pass, order N time and order 1 space. An equivalent view: the answer is the largest prefix sum minus the smallest prefix sum.
Complexity & Mathematical Proof
O(N)
Look at the loop. for x in nums visits each number once. Each visit does two max or min steps and one global update, which is constant work. That is N steps, so time is O(N).
O(1)
The code keeps three variables, curr_max, curr_min and best, whatever the length of nums is. There is no table and no recursion, so space is O(1).
Derivation Progression
for x in nums visits each number once.
3 = O(1)
One max step, one min step and one global update.
3N = O(N)
Numbers times a constant amount of work.
Variable Definitions
Length of nums
Best sum of a subarray ending at the current number, restarting at 0
Worst sum of a subarray ending at the current number, restarting at 0
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(1): the variables curr_max, curr_min and best
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: "the largest absolute sum of any subarray". The absolute value means the best run and the worst run both count, so this is Kadane's Algorithm run twice: once with max and once, mirrored, with min.
and , so a sum is at most , which fits in 32 bits. A loop over all pairs is steps; one pass is .
The empty subarray is allowed here, so max(0, curr_max + x) is correct. Using the non-empty rule max(x, curr_max + x) also works, but then best must start at 0, not at nums[0]. Forgetting -curr_min and tracking only curr_max misses arrays whose largest absolute sum is negative.