Maximum Absolute Sum Of Any Subarray

---

Intuition

• Globally, you wish to find a subarray wherein the difference between the maximum and minimum prefix sums are minimized.
• Why? Since a negative and positive number, when added together, always have a negative impact. Two negatives, when added together and taking the absolute value of that, have a positive impact, and the same is true for when two positives are added together. Given all of those options, in the worst case, you should add a positive sub-array with a negative, with minimal impact.

Complexity

Runtime

$O(N)$

Space

$O(1)$

Code

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        prefixSum = 0
        minPrefixSum = 0
        maxPrefixSum = 0
        for num in nums:
            prefixSum += num
            minPrefixSum = min(minPrefixSum, prefixSum)
            maxPrefixSum = max(maxPrefixSum, prefixSum)
 
        return maxPrefixSum - minPrefixSum

Notes

Cards

START Basic Front: Maximum Absolute Sum Of Any Subarray Back: Greedily store max and min prefix sums, respectively END

---

References

• Maximum Absolute Sum Of Any Subarray