Problem Informations

• Problem Index: 1749
• Problem Link: Maximum Absolute Sum of Any Subarray
• Topics: Array, Dynamic Programming

Problem Description

You are given an integer array nums. The absolute sum of a subarray $[nums_l, nums_{l+1}, …, nums_{r-1}, nums_r]$ is $abs(nums_l + nums_{l+1} + … + nums_{r-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.

Example 1:

Input: nums = [1,-3,2,3,-4]
Output: 5
Explanation: The subarray [2,3] has absolute sum = abs(2+3) = abs(5) = 5.

Example 2:

Input: nums = [2,-5,1,-4,3,-2]
Output: 8
Explanation: The subarray [-5,1,-4] has absolute sum = abs(-5+1-4) = abs(-8) = 8.

Constraints:

• $1 \leq nums.length \leq 10^5$
• $-10^4 \leq nums[i] \leq 10^4$

Intuition

The problem requires finding the maximum absolute sum of a subarray, which could be either entirely positive, entirely negative, or empty (yielding zero). This is essentially a problem of dynamic adjustment of subarray sums while checking their absolute values. Using techniques similar to those in Kadane’s algorithm for maximum subarray sums, we can dynamically calculate both the maximum and minimum possible sums and use them to determine the greatest absolute sum encountered during the traversal.

Approach

The solution involves maintaining two running sums: one for positive subarrays and another for negative subarrays. These correspond to potential positive and negative extremes of subarray sums as the array is traversed.

1. Initialize Variables: We begin by defining three variables:

   • positiveSum: This keeps track of the maximum possible sum of a subarray ending at any given position, where all sums are non-negative. It is initialized to 0.
   • negativeSum: This records the largest possible negative subarray sum. We handle this by treating elements as negative contributions to a subarray (i.e., subtracting instead of adding). It is initialized to 0.
   • maxAbsSum: This holds the highest absolute value of positiveSum or negativeSum encountered and is initially set to 0.

2. Iterate Over the Array: We loop through each element element in nums:

   • Update Positive Sum: Add the current element to positiveSum. If this results in a negative sum, reset positiveSum to zero. This aligns with the fact that a positive subarray sum cannot benefit from negative contributions. $$ \text{positiveSum} = \max(0, \text{positiveSum} + \text{element}) $$
   • Update Negative Sum: Subtract the current element from negativeSum. This simulates treating the element as a positive addition to a negative running sum. If negativeSum becomes less than 0, reset to 0, resetting the context for future potential negative minimum evaluation. $$ \text{negativeSum} = \max(0, \text{negativeSum} - \text{element}) $$

3. Compare and Store Maximum Absolute Sum: For each step, compare the current positiveSum and negativeSum with maxAbsSum and retain the largest. $$ \text{maxAbsSum} = \max(\text{maxAbsSum}, \max(\text{positiveSum}, \text{negativeSum})) $$

4. Return the Result: After processing all elements in nums, maxAbsSum contains the maximum absolute sum of any subarray, which is returned as the result.

Code

C++

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int positiveSum = 0;  // Tracks the maximum positive subarray sum
        int negativeSum = 0;  // Tracks the maximum negative (absolute) subarray sum
        int maxAbsSum = 0;    // Stores the maximum absolute sum found

        for (int element : nums) {
            // Update the positive sum: if adding the current element makes it less than zero, reset to zero
            positiveSum = max(0, positiveSum + element);
            
            // Update the negative sum: treat the element as negative, check the max negative subarray
            negativeSum = max(0, negativeSum - element);
            
            // Compare and store the maximum of current positive, negative sums and the current max absolute sum
            maxAbsSum = max(maxAbsSum, max(positiveSum, negativeSum));
        }

        return maxAbsSum;
    }
};

Python

class Solution:
    def maxAbsoluteSum(self, nums):
        positiveSum = 0  # Tracks the maximum positive subarray sum
        negativeSum = 0  # Tracks the maximum negative (absolute) subarray sum
        maxAbsSum = 0    # Stores the maximum absolute sum found

        for element in nums:
            # Update the positive sum: if adding the current element makes it less than zero, reset to zero
            positiveSum = max(0, positiveSum + element)

            # Update the negative sum: treat the element as negative, check the max negative subarray
            negativeSum = max(0, negativeSum - element)

            # Compare and store the maximum of current positive, negative sums and the current max absolute sum
            maxAbsSum = max(maxAbsSum, max(positiveSum, negativeSum))

        return maxAbsSum

Complexity

• Time complexity: $O(n)$

  The given algorithm iterates through the array nums exactly once, performing a constant amount of work within the loop for each element. Thus, the time complexity is linear with respect to the size of the input array nums, denoted as $n$.

• Space complexity: $O(1)$

  The algorithm uses a constant amount of extra space, regardless of the input size. Variables such as positiveSum, negativeSum, and maxAbsSum are used to store intermediate and final results, and their space usage does not grow with the size of the input array nums. Hence, the space complexity is constant.