Maximum Absolute Sum of Any Subarray

Medium
1143.

Maximum Absolute Sum of Any Subarray

Maximum Absolute Sum of Any Subarray is a medium coding problem on arrays, dynamic programming and prefix sum, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxAbsoluteSum = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Absolute Sum of Any Subarray — Problem & Solution

Maximum Absolute Sum of Any Subarray solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Absolute Sum of Any Subarray is a medium coding problem on arrays, dynamic programming and prefix sum, asked in Amazon and Google interviews.

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

Hints for Maximum Absolute Sum of Any Subarray

  1. Hint 1

    The answer is the larger of the maximum subarray sum and the negated minimum subarray sum.

  2. Hint 2

    Every subarray sum is a difference of two prefix sums P[j] - P[i] with i < j.

  3. Hint 3

    So the largest absolute value of such a difference is simply max(P) - min(P) over all prefix sums, including the empty prefix 0.

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

Java

public static int maxAbsoluteSum(int[] nums) {
    int prefix = 0, hi = 0, lo = 0;
    for (int v : nums) {
        prefix += v;
        hi = Math.max(hi, prefix);
        lo = Math.min(lo, prefix);
    }
    return hi - lo;
}

C++

int maxAbsoluteSum(vector<int>& nums) {
    int prefix = 0, hi = 0, lo = 0;
    for (int v : 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming