Problem Description

You are given an integer array nums. Your task is to find the maximum absolute sum among all possible subarrays (including empty subarrays).

The absolute sum of a subarray is calculated by taking the sum of all elements in that subarray and then applying the absolute value function to the result. For example, if a subarray has elements [a, b, c], its absolute sum would be |a + b + c|.

The absolute value function abs(x) works as follows:

• If x is negative, then abs(x) = -x (makes it positive)
• If x is non-negative, then abs(x) = x (stays the same)

A subarray is a contiguous sequence of elements from the array. It can be empty (in which case the sum would be 0), contain just one element, or contain multiple consecutive elements.

For example, if nums = [1, -3, 2, 3, -4]:

• The subarray [2, 3] has sum 5, so its absolute sum is |5| = 5
• The subarray [-3, 2, 3, -4] has sum -2, so its absolute sum is |-2| = 2
• The subarray [2, 3, -4] has sum 1, so its absolute sum is |1| = 1

Your goal is to return the maximum possible absolute sum among all subarrays of the given array.

Intuition

To find the maximum absolute sum, we need to think about what values could give us the largest result after applying the absolute value function. The key insight is that the maximum absolute sum could come from either:

1. A subarray with the largest positive sum
2. A subarray with the most negative sum (which becomes positive after applying absolute value)

This means we need to track both extremes - the maximum sum and the minimum sum possible for subarrays ending at each position.

Think of it this way: if we're looking for max(|sum|), this is equivalent to finding max(maximum_sum, |minimum_sum|). Since the absolute value of the most negative number could be larger than the most positive number, we can't just look for the maximum sum alone.

For example, if we have an array like [1, -3, -4]:

• The maximum sum subarray might be [1] with sum 1
• But the minimum sum subarray is [-3, -4] with sum -7
• After applying absolute value, |-7| = 7 is larger than 1

This leads us to use a dynamic programming approach where we maintain two running values:

• f: tracks the maximum sum of subarrays ending at the current position
• g: tracks the minimum sum of subarrays ending at the current position

At each position, we decide whether to extend the previous subarray or start fresh:

• For maximum: f = max(f + current_element, current_element) which simplifies to max(f, 0) + current_element
• For minimum: g = min(g + current_element, current_element) which simplifies to min(g, 0) + current_element

The answer is the maximum among all the maximum sums and the absolute values of all the minimum sums encountered during the traversal.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution implements a dynamic programming approach using Kadane's algorithm variant that tracks both maximum and minimum subarray sums simultaneously.

Implementation Details:

We use two variables to maintain our dynamic programming states:

• f: represents the maximum sum of subarrays ending at the current position
• g: represents the minimum sum of subarrays ending at the current position
• ans: keeps track of the maximum absolute sum found so far

Algorithm Steps:

1. Initialize f = 0 and g = 0 as the maximum and minimum sums before processing any elements
2. Initialize ans = 0 to store the result
3. For each element x in the array:
   • Update maximum sum: f = max(f, 0) + x
     • This means: either extend the previous maximum subarray (f + x) or start a new subarray from current element (0 + x)
   • Update minimum sum: g = min(g, 0) + x
     • This means: either extend the previous minimum subarray (g + x) or start a new subarray from current element (0 + x)
   • Update answer: ans = max(ans, f, abs(g))
     • Compare current answer with the new maximum sum and the absolute value of the new minimum sum

State Transition Equations:

The core logic follows these recurrence relations:

f[i] = max(f[i-1], 0) + nums[i]
g[i] = min(g[i-1], 0) + nums[i]

Where:

• f[i] represents the maximum sum ending at index i
• g[i] represents the minimum sum ending at index i

Space Optimization:

Instead of using arrays to store all f[i] and g[i] values, we only need the previous state to compute the current state. This optimization reduces space complexity from O(n) to O(1).

Time and Space Complexity:

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(1) - only using constant extra space for variables

Example Walkthrough

Let's walk through the solution with nums = [2, -5, 1, -4, 3, -2]

We'll track three variables:

• f: maximum sum ending at current position
• g: minimum sum ending at current position
• ans: maximum absolute sum found so far

Initial state: f = 0, g = 0, ans = 0

Step 1: Process element 2

• f = max(0, 0) + 2 = 2 (start new subarray [2])
• g = min(0, 0) + 2 = 2 (start new subarray [2])
• ans = max(0, 2, |2|) = 2

Step 2: Process element -5

• f = max(2, 0) + (-5) = -3 (extend to [2, -5])
• g = min(2, 0) + (-5) = -5 (start new subarray [-5])
• ans = max(2, -3, |-5|) = 5

Step 3: Process element 1

• f = max(-3, 0) + 1 = 1 (start new subarray [1])
• g = min(-5, 0) + 1 = -4 (extend to [-5, 1])
• ans = max(5, 1, |-4|) = 5

Step 4: Process element -4

• f = max(1, 0) + (-4) = -3 (extend to [1, -4])
• g = min(-4, 0) + (-4) = -8 (extend to [-5, 1, -4])
• ans = max(5, -3, |-8|) = 8

Step 5: Process element 3

• f = max(-3, 0) + 3 = 3 (start new subarray [3])
• g = min(-8, 0) + 3 = -5 (extend to [-5, 1, -4, 3])
• ans = max(8, 3, |-5|) = 8

Step 6: Process element -2

• f = max(3, 0) + (-2) = 1 (extend to [3, -2])
• g = min(-5, 0) + (-2) = -7 (extend to [-5, 1, -4, 3, -2])
• ans = max(8, 1, |-7|) = 8

Final answer: 8 (from the subarray [-5, 1, -4] with sum -8, giving absolute sum 8)

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because the algorithm iterates through the array exactly once, performing constant-time operations (max, min, abs, and arithmetic operations) for each element.

The space complexity is O(1), as the algorithm only uses a fixed amount of extra space regardless of the input size. It maintains three variables (f, g, and ans) that store intermediate results, and these variables do not grow with the size of the input array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Consider Both Positive and Negative Sums

The Problem: A common mistake is to only track the maximum sum subarray and take its absolute value, missing cases where the minimum (most negative) sum subarray actually has a larger absolute value.

Example of Incorrect Approach:

def maxAbsoluteSum(self, nums: List[int]) -> int:
    max_sum = 0
    current_sum = 0
  
    for num in nums:
        current_sum = max(current_sum + num, num, 0)
        max_sum = max(max_sum, abs(current_sum))
  
    return max_sum

This would fail for nums = [2, -5, 1, -4, 3, -2] where the minimum sum subarray [-5, 1, -4] has sum -8 and absolute value 8, which is larger than any positive subarray sum.

Solution: Always track both the maximum and minimum sums simultaneously, as shown in the correct implementation.

Pitfall 2: Incorrect State Transition Logic

The Problem: Misunderstanding how to update the maximum and minimum sums can lead to incorrect results. A common error is:

# INCORRECT
max_sum = max(max_sum + num, num)  # Missing the "start fresh with 0" option
min_sum = min(min_sum + num, num)  # Missing the "start fresh with 0" option

This forces every subarray to include at least one element, which misses the case where it's better to "reset" and start a new subarray.

Solution: Use the correct transition formulas:

max_sum = max(max_sum, 0) + num  # Can choose to start fresh (0) or extend
min_sum = min(min_sum, 0) + num  # Can choose to start fresh (0) or extend

Pitfall 3: Not Initializing Variables Correctly

The Problem: Initializing max_sum or min_sum to the first element or to very large/small values:

# INCORRECT
max_sum = nums[0]  # Wrong initialization
min_sum = nums[0]  # Wrong initialization

This prevents the algorithm from correctly considering empty subarrays or properly resetting when needed.

Solution: Initialize both max_sum and min_sum to 0, representing empty subarrays before processing any elements.

Pitfall 4: Forgetting Edge Cases

The Problem: Not handling arrays with all positive or all negative numbers correctly, or forgetting that the empty subarray (sum = 0) is valid.

Example: For nums = [-1, -2, -3], the maximum absolute sum should be 6 (from subarray [-1, -2, -3]), not 3.

Solution: The algorithm naturally handles these cases by tracking both maximum and minimum sums and always considering the option to start fresh (empty subarray).