Maximum Absolute Sum of Any Subarray

1. Define the problem

Maximum Absolute Sum of Any Subarray

Given an integer array nums, find a subarray whose sum has the largest absolute value and return that absolute value. A subarray with a very negative sum is just as extreme as one with a very positive sum, so run two Kadane passes at once : one tracking the best positive-leaning running sum ending here, and one tracking the best negative-leaning running sum ending here.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums_i ≤ 10⁴

Example

Inputnums = [1, -3, 2, 3, -4]

Output5

Explanation The subarray [2, 3] sums to 5, which has the largest absolute value.

2. Know the words first

In plain terms

Absolute value: A number's distance from zero, ignoring its sign — |5| and |-5| are both 5.
Two Kadane passes at once: Two running values updated together at every index: one resets to 0 whenever extending would drag it below 0 (chasing the largest positive sum), the other resets to 0 whenever extending would push it above 0 (chasing the most negative sum).

3. Visualize the solution

Track a positive-leaning and a negative-leaning running sum together

1-3

4-4

Statuscurrent: +1 / -1 · best: 1

Both running sums start at 0. Adding the first element, 1, gives a best of 1 from the framed subarray [1].

What happens in this step

num = 1

maxEnding = max(0, maxEnding) + num = max(0, 0) + 1 = 1
minEnding = min(0, minEnding) + num = min(0, 0) + 1 = 1
best = max(best, maxEnding, -minEnding) = max(0, 1, -1) = 1

Both running sums start at 0; adding the first element gives both a value of 1, so best becomes 1 and the frame sits on index 0.

Step 1 of 5

Steps to visualize

The row is the whole input array, [1, -3, 2, 3, -4]. The frame marks the subarray with the largest absolute sum found so far.
Start both running sums at 0.
At each index, extend the positive-leaning sum only if doing so keeps it at or above 0, otherwise reset it to 0 at this element.
Extend the negative-leaning sum only if doing so keeps it at or below 0, otherwise reset it to 0 at this element.
The best-so-far is the larger of the positive-leaning sum and the absolute value of the negative-leaning sum.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Track a positive-leaning and a negative-leaning running sum together

1-3

4-4

Statuscurrent: +1 / -1 · best: 1

Both running sums start at 0. Adding the first element, 1, gives a best of 1 from the framed subarray [1].

What happens in this step

num = 1

maxEnding = max(0, maxEnding) + num = max(0, 0) + 1 = 1
minEnding = min(0, minEnding) + num = min(0, 0) + 1 = 1
best = max(best, maxEnding, -minEnding) = max(0, 1, -1) = 1

Both running sums start at 0; adding the first element gives both a value of 1, so best becomes 1 and the frame sits on index 0.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function maxAbsoluteSum(nums) {
  let maxEnding = 0;
  let minEnding = 0;
  let best = 0;

  for (const num of nums) {
    maxEnding = Math.max(0, maxEnding) + num;
    minEnding = Math.min(0, minEnding) + num;
    best = Math.max(best, maxEnding, -minEnding);
  }

  return best;
}

Time: O(n)
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, -3, 2, 3, -4]`	`5`	example from the docstring
`nums = [2, -5, 1, -4, 3, -2]`	`8`	the most extreme subarray is negative, not positive
`nums = [-1, -2, -3]`	`6`	every value negative — the whole array is the most extreme subarray
`nums = [1, 2, 3]`	`6`	every value positive — the whole array is the most extreme subarray
`nums = [5]`	`5`	smallest valid input, a single positive element
`nums = [-5]`	`5`	smallest valid input, a single negative element
`nums = [0, 0, 0]`	`0`	every value is zero, no subarray can beat zero
`nums = [0, 3, -4, 5]`	`5`	a leading zero and a mix of signs, single element wins

Maximum Absolute Sum of Any Subarray