Problem Statement in English

You’re given an integer array nums. Return the maximum absolute sum of any (possibly empty) subarray of nums.

Approach

This is quite similar to anothe problem I’ve covered (1524).

The idea is to simulate the generation of the subarrays that we care about. We can do this by keeping track of the biggest positive and negative subarray sum we’ve encountered up until now.

  • If the current subarray sum we have is negative, then we can subtract the biggest negative subarray sum we’ve encountered so far to get the maximum absolute sum.

  • If the current subarray sum we have is positive, then we can subtract the biggest positive subarray sum we’ve encountered so far to get the maximum absolute sum.

And..that’s about it.

Solution in Python


class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        prefix_sums = [nums[0]]

        for num in nums[1:]:
            prefix_sums.append(prefix_sums[-1]+num)

        pos_val, neg_val = 0, 0
        res = abs(prefix_sums[0])

        for ps in prefix_sums:
            if ps < 0:
                res = max(res, abs(ps-pos_val))
            else:
                res = max(res, abs(ps-neg_val))

            if ps < neg_val:
                neg_val = ps
            elif ps > pos_val:
                pos_val = ps

        return res

Complexity

  • Time: $O(n)$
    Since we iterate through all the elements in the array.

  • Space: $O(n)$
    Since we store the prefix sums in an array. However, we can do this in-place to reduce the space complexity to $O(1)$.

And we are done.