How to Find the Subarray with Maximum Absolute Sum – LeetCode 1749 Solution

Problem Description

Platform: LeetCode

Problem number: 1749

Given an integer array nums, the absolute sum of a subarray [l, l+1, ..., r] is abs(nums[l] + nums[l+1] + ... + nums[r]).

Find any subarray (possibly empty) whose absolute sum is maximum and return that value.

Definition of abs(x)

If x is a negative integer, abs(x) = -x.

If x is a non‑negative integer, abs(x) = x.

Examples

Input: nums = [1,-3,2,3,-4]
Output: 5
Explanation: Subarray [2,3] has the maximum absolute sum, |2+3| = 5.

Input: nums = [2,-5,1,-4,3,-2]
Output: 8
Explanation: Subarray [-5,1,-4] gives |-5+1-4| = 8.

Solution Overview

The problem asks for the maximum absolute sum of any contiguous subarray, which can be solved efficiently with prefix sums.

Let sum[i] be the prefix sum up to index i. The sum of subarray [i, j] equals sum[j] - sum[i-1]. The maximum absolute value of this difference is obtained either by the largest prefix minus the smallest earlier prefix or vice‑versa.

Thus we only need to track the running minimum and maximum prefix sums while iterating, updating the answer with the absolute differences.

Complexities

Time complexity: O(n)

Space complexity: O(n) for the prefix array (can be reduced to O(1) if desired)

Reference Implementations

Java:

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n = nums.length, ans = 0;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        int min = 0, max = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, Math.abs(sum[i] - min));
            ans = Math.max(ans, Math.abs(sum[i] - max));
            max = Math.max(max, sum[i]);
            min = Math.min(min, sum[i]);
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        vector<int> sumv(n + 1, 0);
        for (int i = 1; i <= n; i++) sumv[i] = sumv[i - 1] + nums[i - 1];
        int minv = 0, maxv = 0;
        for (int i = 1; i <= n; i++) {
            ans = max(ans, abs(sumv[i] - minv));
            ans = max(ans, abs(sumv[i] - maxv));
            maxv = max(maxv, sumv[i]);
            minv = min(minv, sumv[i]);
        }
        return ans;
    }
};

Python:

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        n, ans = len(nums), 0
        sumv = [0] * (n + 1)
        for i in range(1, n + 1):
            sumv[i] = sumv[i - 1] + nums[i - 1]
        minv, maxv = 0, 0
        for i in range(1, n + 1):
            ans = max(ans, abs(sumv[i] - minv))
            ans = max(ans, abs(sumv[i] - maxv))
            maxv = max(maxv, sumv[i])
            minv = min(minv, sumv[i])
        return ans

TypeScript:

function maxAbsoluteSum(nums: number[]): number {
    const n = nums.length;
    let ans = 0;
    const sum = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
    let min = 0, max = 0;
    for (let i = 1; i <= n; i++) {
        ans = Math.max(ans, Math.abs(sum[i] - min));
        ans = Math.max(ans, Math.abs(sum[i] - max));
        max = Math.max(max, sum[i]);
        min = Math.min(min, sum[i]);
    }
    return ans;
}