Problem Description

Given an integer array nums, your task is to find the maximum absolute sum of any subarray within nums.
A subarray is a contiguous, non-empty sequence of elements from the array. The absolute sum of a subarray is the absolute value of the sum of its elements.
Return the largest possible absolute sum among all possible subarrays of nums.
Constraints:

• 1 ≤ nums.length ≤ 10⁵
• -10⁴ ≤ nums[i] ≤ 10⁴

Thought Process

At first glance, the problem seems to ask for the subarray with the largest sum in magnitude, regardless of sign. For example, a subarray sum of 15 or -15 both have an absolute sum of 15.
A brute-force approach would be to check every possible subarray, calculate its sum, take the absolute value, and track the maximum. However, this is highly inefficient for large arrays.
This problem is closely related to the classic "Maximum Subarray Sum" (Kadane's Algorithm), but now we must also consider the minimum (most negative) sum, since its absolute value could be the largest. The key realization is that the maximum absolute sum is either the largest positive subarray sum or the smallest (most negative) subarray sum, whichever has the larger magnitude.

Solution Approach

We can solve this problem efficiently using a modified version of Kadane's Algorithm:

• Step 1: Initialize two variables:
  • max_sum to track the maximum subarray sum (Kadane's original)
  • min_sum to track the minimum subarray sum (for negative values)
• Step 2: Iterate through nums:
  • For max_sum: At each step, set current_max = max(num, current_max + num).
  • For min_sum: At each step, set current_min = min(num, current_min + num).
  • Update max_sum and min_sum as the maximum/minimum seen so far.
• Step 3: The answer is max(abs(max_sum), abs(min_sum)).

This approach ensures we check both the largest positive and largest negative (in magnitude) subarray sums in a single pass.

Example Walkthrough

Example: nums = [1, -3, 2, 3, -4]
Let's go step by step:

• Start: current_max = 0, current_min = 0, max_sum = 0, min_sum = 0
• 1: current_max = max(1, 0+1) = 1, max_sum = 1; current_min = min(1, 0+1) = 1, min_sum = 0
• -3: current_max = max(-3, 1-3) = -2, max_sum = 1; current_min = min(-3, 1-3) = -3, min_sum = -3
• 2: current_max = max(2, -2+2) = 2, max_sum = 2; current_min = min(2, -3+2) = -1, min_sum = -3
• 3: current_max = max(3, 2+3) = 5, max_sum = 5; current_min = min(3, -1+3) = 2, min_sum = -3
• -4: current_max = max(-4, 5-4) = 1, max_sum = 5; current_min = min(-4, 2-4) = -4, min_sum = -4

Final result: max(abs(5), abs(-4)) = 5

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(N²) — There are O(N²) subarrays and summing each takes O(1) to O(N).
• Space Complexity: O(1) — Only a few variables needed.

• Time Complexity: O(N) — We traverse the array once.
• Space Complexity: O(1) — Only a fixed number of variables are used.

The optimized approach is critical for handling large input sizes efficiently.

Summary

The core insight is that the maximum absolute sum of a subarray is either the largest positive subarray sum or the smallest (most negative) subarray sum in magnitude. By running Kadane's algorithm twice—once for the maximum and once for the minimum—we can find both efficiently in a single pass. This approach is elegant, avoids brute-force enumeration, and leverages a classic dynamic programming technique.

Code Implementation

class Solution:
    def maxAbsoluteSum(self, nums):
        max_sum = min_sum = 0
        current_max = current_min = 0
        for num in nums:
            current_max = max(num, current_max + num)
            max_sum = max(max_sum, current_max)
            current_min = min(num, current_min + num)
            min_sum = min(min_sum, current_min)
        return max(abs(max_sum), abs(min_sum))
      

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

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int maxSum = 0, minSum = 0;
        int currentMax = 0, currentMin = 0;
        for (int num : nums) {
            currentMax = Math.max(num, currentMax + num);
            maxSum = Math.max(maxSum, currentMax);
            currentMin = Math.min(num, currentMin + num);
            minSum = Math.min(minSum, currentMin);
        }
        return Math.max(Math.abs(maxSum), Math.abs(minSum));
    }
}
      

var maxAbsoluteSum = function(nums) {
    let maxSum = 0, minSum = 0;
    let currentMax = 0, currentMin = 0;
    for (let num of nums) {
        currentMax = Math.max(num, currentMax + num);
        maxSum = Math.max(maxSum, currentMax);
        currentMin = Math.min(num, currentMin + num);
        minSum = Math.min(minSum, currentMin);
    }
    return Math.max(Math.abs(maxSum), Math.abs(minSum));
};