Maximum Absolute Sum of Any Subarray

Leetcode Problem:

• Maximum Absolute Sum of Any Subarray

Summary

• Given an integer array, find the maximum absolute sum of any subarray.

Approach

• Use two pointers to track the maximum and minimum prefix sum, then return the maximum of the two absolute values.

Complexity

• O(n) where n is the number of elements in the array

Explanation

• The solution works by iterating over the array twice, once to find the maximum prefix sum and once to find the minimum prefix sum
• The maximum prefix sum is updated whenever a positive number is encountered, and the minimum prefix sum is updated whenever a negative number is encountered
• The maximum of the two absolute values is then returned as the result.

Solution Code:

class Solution {
public:
    int maxAbsoluteSum(vector& nums) {
        int r = 0;
        int l = 0;
        int plusMax = 0;
        int prefixSum = 0;
        for(int num : nums){
            prefixSum += num;
            if(prefixSum < 0) prefixSum = 0;
            plusMax = max(plusMax, prefixSum);
        }

        int minusMin = 0;
        prefixSum = 0;
        for(int num:nums){
            prefixSum += num;
            if(prefixSum > 0) prefixSum = 0;
            minusMin = min(minusMin, prefixSum);
        }
        return plusMax > abs(minusMin) ? plusMax : abs(minusMin);
    }
};