Leetcode 1749. Maximum Absolute Sum of Any Subarray

Problem Description

#

You are given an integer array nums. The absolute sum of a subarray [nums_l , nums_{l+1}, ... , nums_r] is abs(nums_l + nums_{l+1} + ... + nums_r).

Return the maximum absolute sum of any (possibly empty) subarray of nums.

Note that abs(x) is defined as follows:

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

Solution - Prefix Sum

#

• We know that the sum of a subarray is equal to minus of two prefix sum of array.
• Hence, the maximum absolute sum is equal to the maximum prefix sum of array minus the minimum of prefix sum.

Code

#

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int prefixSum = 0;
        int maxSum = 0;
        int minSum = 0;
        for(int num : nums){
            prefixSum += num;
            maxSum = max(prefixSum, maxSum);
            minSum = min(prefixSum, minSum);
        }
        return maxSum - minSum;
    }
};

• Time complexity: $O(n)$
• Space complexity: $O(1)$

Thank you for reading! Let me know your thoughts and feedback! {: .prompt-tip }