LeetCode 1749 - Maximum Absolute Sum of Any Subarray

LeetCode Problem 1749

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to calculate the maximum absolute sum of any contiguous subarray in a given integer array nums. A subarray is a sequence of consecutive elements, and its absolute sum is defined as the absolute value of the sum of all elements in that subarray.

In other words, for a subarray [nums[l], nums[l+1], ..., nums[r]], we calculate sum(nums[l:r+1]) and then take abs(sum). The task is to find the largest possible absolute sum across all possible subarrays, including the empty subarray (whose sum is zero).

The input is an integer array nums of length up to 100,000 with each element ranging from -10,000 to 10,000. The constraints imply that a naive brute-force solution that checks all possible subarrays, which would be O(n²) in time, is too slow. The solution must be efficient, ideally linear.

Edge cases to consider include arrays where all numbers are positive, all numbers are negative, or arrays with a mix of positive and negative numbers that may cancel each other out.

Approaches

The brute-force approach would consider all subarrays, calculate their sums, and track the maximum absolute value. This works correctly but is highly inefficient because the number of subarrays is O(n²), and summing each subarray takes O(n) time, resulting in O(n³) total time.

The key observation for an optimal solution is that the problem reduces to a variant of the maximum subarray sum problem (Kadane’s algorithm). Instead of just tracking the maximum sum, we track both the maximum sum and the minimum sum subarrays. The absolute maximum will then be the greater of max_sum and abs(min_sum). This works because a subarray with a large negative sum has an absolute value that might exceed all positive sums.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Compute sum of all subarrays and take max absolute value
Optimal	O(n)	O(1)	Use modified Kadane’s algorithm for max and min subarray sums

Algorithm Walkthrough

1. Initialize two variables: max_sum to track the maximum subarray sum ending at the current index, and min_sum to track the minimum subarray sum ending at the current index. Also, initialize max_abs_sum to track the maximum absolute sum encountered so far.
2. Initialize two accumulators: current_max and current_min both set to 0. These represent the best subarray sums ending at the current element.
3. Iterate over each number x in nums.
4. Update current_max as the maximum of x and current_max + x. This is the standard Kadane’s step for maximum sum subarray ending at the current element.
5. Update current_min as the minimum of x and current_min + x. This tracks the minimum (most negative) sum ending at the current element.
6. Update max_abs_sum as the maximum of itself, current_max, and abs(current_min).
7. After the loop, max_abs_sum contains the maximum absolute sum of any subarray.

Why it works: At each step, current_max ensures we capture the largest possible subarray sum ending at the current index, while current_min ensures we capture the most negative subarray sum. Taking the absolute value of the minimum accounts for the largest negative contribution. Since every subarray is contiguous and Kadane’s algorithm considers all possible endpoints efficiently, the result is correct.

Python Solution

from typing import List

class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        max_abs_sum = 0
        current_max = 0
        current_min = 0
        
        for x in nums:
            current_max = max(x, current_max + x)
            current_min = min(x, current_min + x)
            max_abs_sum = max(max_abs_sum, current_max, abs(current_min))
        
        return max_abs_sum

The implementation directly follows the algorithm walkthrough. current_max computes the maximum subarray sum ending at the current element, while current_min tracks the minimum. The max_abs_sum is updated in each iteration to ensure it always contains the largest absolute sum encountered.

Go Solution

func maxAbsoluteSum(nums []int) int {
    maxAbsSum := 0
    currentMax := 0
    currentMin := 0

    for _, x := range nums {
        if currentMax + x > x {
            currentMax = currentMax + x
        } else {
            currentMax = x
        }

        if currentMin + x < x {
            currentMin = currentMin + x
        } else {
            currentMin = x
        }

        if currentMax > maxAbsSum {
            maxAbsSum = currentMax
        }
        if -currentMin > maxAbsSum {
            maxAbsSum = -currentMin
        }
    }

    return maxAbsSum
}

In Go, the main differences are explicit if-statements instead of max/min functions, and the loop iterates with the range keyword. The logic remains identical to the Python version.

Worked Examples

Example 1: nums = [1,-3,2,3,-4]

i	x	current_max	current_min	max_abs_sum
0	1	1	1	1
1	-3	-2	-3	3
2	2	2	-1	3
3	3	5	-1	5
4	-4	1	-4	5

Result: 5

Example 2: nums = [2,-5,1,-4,3,-2]

i	x	current_max	current_min	max_abs_sum
0	2	2	2	2
1	-5	-3	-5	5
2	1	1	-4	5
3	-4	-3	-8	8
4	3	3	-5	8
5	-2	1	-7	8

Result: 8

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array, updating current max and min sums
Space	O(1)	Only a few integer variables are used regardless of input size

Since each element is processed exactly once and no additional data structures are needed, the solution is optimal.

Test Cases

# Provided examples
assert Solution().maxAbsoluteSum([1,-3,2,3,-4]) == 5  # Example 1
assert Solution().maxAbsoluteSum([2,-5,1,-4,3,-2]) == 8  # Example 2

# All positive numbers
assert Solution().maxAbsoluteSum([1,2,3,4]) == 10  # sum of entire array

# All negative numbers
assert Solution().maxAbsoluteSum([-1,-2,-3,-4]) == 10  # abs(sum of entire array)

# Single element
assert Solution().maxAbsoluteSum([7]) == 7
assert Solution().maxAbsoluteSum([-7]) == 7

# Alternating positive and negative
assert Solution().maxAbsoluteSum([1,-1,2,-2,3,-3]) == 3

# Large numbers
assert Solution().maxAbsoluteSum([10000, -10000, 10000, -10000]) == 10000

Test	Why
[1,-3,2,3,-4]	Validates a small mix of positive and negative numbers
[2,-5,1,-4,3,-2]	Larger mix with consecutive negative sum
[1,2,3,4]	All positive, should sum the whole array
[-1,-2,-3,-4]	All negative, absolute value matters
[7], [-7]	Single element edge cases
[1,-1,2,-2,3,-3]	Alternating signs, subarray selection is critical
[10000,-10000,10000,-10000]	Large numbers to test potential overflow

Edge Cases

One edge case is a single-element array. The solution correctly returns the absolute value of that element, handling both positive and negative cases.

Another important edge case is an array with all negative numbers. The naive implementation that only tracks the maximum sum could fail here, but tracking the minimum ensures the absolute value is considered.

A third edge case is when the maximum absolute sum comes from a subarray that is not the full array but an internal portion. For example, [1,-3,2,3,-4] has the subarray [2,3] giving the maximum absolute sum of 5. Kadane’s algorithm adapted for both