Maximum Absolute Sum of Any Subarray

Problem Id: 1749 Difficulty: Medium Tag: Greedy


Intuition

First knowledge you need to know to do this problem is that, to quickly calculate the sub of a sub-array nums[i:j] for every different i and j, you can use another array where sum_nums[i] = sum(nums[:i]). And then, sum(nums[i:j]) = sum_nums[j] - sum_nums[i].

With this knowledge, everything because so simple. For this problem, you need to get the difference between the biggest and smallest value of sum_nums.

Further more, we don't need to store the whole sum_nums. Instead, we only need to store the biggest and the smallest value.

Solution


class Solution:
    def maxAbsoluteSum(self, nums):
        s = 0
        big = 0
        small = 0
        max_abs = 0
        for num in nums:
            s += num
            small = min(s, small)
            big = max(s, big)

            max_abs = max(
                max_abs,
                abs(big - s),
                abs(small - s)
            )
        return max_abs