Maximum Absolute Sum of Any Subarray — Medium Problem & Solution

Problem statement

The absolute sum of a subarray [nums[l], ..., nums[r]] is |nums[l] + ... + nums[r]|.

Return the maximum absolute sum over all subarrays of nums. The subarray may be empty, with absolute sum 0.

Example 1

Input: nums = [3,-5,1,-6,2]
Output: 10
Explanation: `[-5,1,-6]` sums to -10.

Example 2

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

Example 3

Input: nums = [4]
Output: 4

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

How to solve Maximum Absolute Sum of Any Subarray

A subarray's sum is a difference of two prefix sums, and the largest absolute difference between any two prefix sums is the gap between the largest and smallest one.

Approach

1. Sweep the array keeping the running prefix sum, starting from 0.
2. Track the maximum and minimum prefix sums seen (both start at 0, the empty prefix).
3. Return maxPrefix - minPrefix.

Why it works

For any two prefix positions the absolute difference is the absolute sum of the subarray between them, regardless of which comes first. So the best absolute sum is the largest difference between two prefix sums, which is attained by the maximum and the minimum.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Forgetting the empty prefix (0) misses subarrays that start at index 0.
• Running only Kadane for the maximum misses strongly negative subarrays.
• The answer is at most 10^9 under these bounds, so it fits in 32 bits.

Reference solution

Python

from typing import List

def maxAbsoluteSum(nums: List[int]) -> int:
    prefix = hi = lo = 0
    for v in nums:
        prefix += v
        hi = max(hi, prefix)
        lo = min(lo, prefix)
    return hi - lo

JavaScript

var maxAbsoluteSum = function(nums) {
    var prefix = 0, hi = 0, lo = 0;
    for (var i = 0; i < nums.length; i++) {
        prefix += nums[i];
        if (prefix > hi) hi = prefix;
        if (prefix < lo) lo = prefix;
    }
    return hi - lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium