Maximum Absolute Sum of Any Subarray: Prefix Sum Extremes

You are given an integer array nums. Find the maximum absolute sum of any (possibly empty) subarray of nums. A subarray is a contiguous part of the array.

This is LeetCode 1749: Maximum Absolute Sum of Any Subarray, and it is a natural extension of the classic Maximum Subarray problem. The twist here is that you care about both the most positive and the most negative subarray sums, because either one could produce the largest absolute value.

Why this problem matters

If you have solved the classic maximum subarray problem with Kadane's algorithm, you already understand how to find the largest subarray sum in one pass. This problem asks you to generalize that thinking. Instead of only caring about the maximum sum, you also need to consider the minimum sum, because a very negative subarray sum has a large absolute value too.

This connects to a broader pattern in subarray problems: prefix sums. Many subarray sum questions reduce to tracking properties of prefix sums, and this problem is one of the cleanest examples. The subarray sum between any two indices i and j is just prefix[j] - prefix[i]. Once you see that, the problem transforms from "find the best subarray" into "find the widest gap in a prefix sum sequence."

Understanding this reduction pays off across many problems. Subarray Sum Equals K uses prefix sums with a hash map. Maximum Subarray is a special case where you only need the max. Here, you need both the max and the min of the prefix sums, and that is the entire algorithm.

The key insight

The sum of any subarray nums[i..j] equals prefix[j+1] - prefix[i], where prefix[k] is the sum of the first k elements and prefix[0] = 0.

To maximize the absolute value of a subarray sum, you want to maximize |prefix[j] - prefix[i]| for some pair i, j. The maximum absolute difference between any two values in a sequence is simply max(sequence) - min(sequence).

So the answer is: compute prefix sums, and return maxPrefix - minPrefix. You do not even need to store the entire prefix array. Just track the running max and min as you go.

The solution

def max_absolute_sum(nums):
    prefix = 0
    max_prefix = 0
    min_prefix = 0

    for num in nums:
        prefix += num
        max_prefix = max(max_prefix, prefix)
        min_prefix = min(min_prefix, prefix)

    return max_prefix - min_prefix

The logic is almost too simple. You walk through the array, maintaining a running prefix sum. At each step, you update the maximum and minimum prefix sums you have seen so far. At the end, the answer is just the difference between those two extremes.

Why does this work? Every subarray sum nums[i] + nums[i+1] + ... + nums[j] equals prefix[j+1] - prefix[i]. The largest absolute value of such a difference occurs when one prefix is as large as possible and the other is as small as possible. By tracking max_prefix and min_prefix independently, you capture exactly that pair.

Notice that prefix[0] = 0 is implicitly included because we initialize both max_prefix and min_prefix to 0. This accounts for subarrays that start at the beginning of the array.

Visual walkthrough

The prefix sums are [0, 1, -2, 0, 3, -1]. The maximum prefix sum is 3 (at index 4), and the minimum is -2 (at index 2). The answer is 3 - (-2) = 5.

This corresponds to two subarrays. The subarray [2, 3] (indices 2 to 3) has sum 5. The subarray [-3, 2, 3, -4] (indices 1 to 4) has sum -2, giving absolute value 2. But the maximum absolute sum is 5 either way, because the prefix sum gap captures the best option regardless of sign.

Complexity analysis

Time: O(n). You make a single pass through the array. Each element requires O(1) work: one addition, two comparisons. Total is O(n).

Space: O(1). Three variables: prefix, max_prefix, and min_prefix. No extra arrays or data structures needed, regardless of input size.

The building blocks

1. Prefix sum tracking

The core idea is that any subarray sum can be expressed as a difference of two prefix sums. Rather than computing all O(n^2) subarray sums, you compute n prefix sums in one pass.

prefix = 0
for num in nums:
    prefix += num

This single loop gives you all the information you need. The subarray sum from index i to j (inclusive) is prefix_after_j - prefix_before_i.

2. Max and min tracking in one pass

Once you have the prefix sums flowing through, you just need to track the extreme values.

max_prefix = max(max_prefix, prefix)
min_prefix = min(min_prefix, prefix)

This is the same "running max" pattern from Best Time to Buy and Sell Stock, where you track the minimum price seen so far. Here, you track both the maximum and minimum prefix sums seen so far. Two variables, zero extra passes.

Edge cases

• All positive like [1, 2, 3]: the max prefix is 6, min prefix is 0. Answer is 6 (the total sum).
• All negative like [-3, -5, -1]: the max prefix is 0, min prefix is -9. Answer is 9 (the absolute value of the total sum).
• Single element [5]: answer is 5. [-3]: answer is 3.
• Alternating signs like [1, -1, 1, -1]: prefix sums oscillate between 0 and 1. Max prefix = 1, min prefix = 0. Answer is 1.
• Contains zero like [0, 0, 0]: all prefix sums are 0. Answer is 0.

The algorithm handles all of these with no special cases. The key is that initializing both max_prefix and min_prefix to 0 automatically includes the empty prefix, which is correct because prefix[0] = 0 is always part of the prefix sum sequence.

From understanding to recall

You have just read through the prefix sum max-min approach and the math makes perfect sense. The answer is maxPrefix - minPrefix. But in an interview, you need to produce this from scratch. You need to remember to initialize both trackers to 0 (not to the first element), and you need to recall why the absolute value trick works through prefix sums rather than through Kadane's algorithm run twice.

Spaced repetition is designed for exactly this gap between understanding and recall. Instead of solving this problem once and forgetting the prefix sum reduction in two weeks, you revisit the pattern at increasing intervals. Each time you write the three-variable solution from memory. After a few reps, the prefix-max-min template is automatic, and you can apply it to any problem that reduces to "find the widest gap in a running sum."

Related posts

• Maximum Subarray - The classic Kadane's algorithm for max subarray sum
• Maximum Product Subarray - Extends subarray tracking to products
• Subarray Sum Equals K - Uses prefix sums with hash map for target sum

CodeBricks breaks problems like this into reusable building blocks (prefix sum tracking, running min/max) and drills them with spaced repetition so the patterns stick. Instead of memorizing solutions, you internalize the pieces that compose them.