Maximum Absolute Sum of Any Subarray

Med

#1601Time: O(n^2), where n is the number of elements in the input array. The nested loops lead to a quadratic number of operations.Space: O(1), as we only use a constant amount of extra space for variables like `maxAbsSum` and `currentSum`.

Patterns

Dynamic Programming

Data structures

Array

Prompt

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 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through all possible contiguous subarrays, calculating the sum of each one, and keeping track of the maximum absolute sum found. To avoid a third nested loop for calculating the sum, a running sum is maintained as we extend the subarray from a fixed starting point.

Algorithm

Initialize maxAbsSum to 0.
Iterate through the array with an index i from 0 to n-1 to select the starting element of the subarray.
Inside this loop, initialize currentSum to 0.
Start a nested loop with an index j from i to n-1 to select the ending element of the subarray.
In the inner loop, add nums[j] to currentSum.
Update maxAbsSum with max(maxAbsSum, abs(currentSum)).
After both loops complete, return maxAbsSum.

Walkthrough

The brute-force method systematically checks every possible subarray. A subarray is defined by its start and end indices. We can use two nested loops to generate all such pairs of indices.

The outer loop (with index i) determines the starting point of the subarray. The inner loop (with index j) determines the ending point. For each starting point i, we initialize a currentSum to zero. As the inner loop progresses from i to the end of the array, we add the current element nums[j] to currentSum. This currentSum represents the sum of the subarray nums[i...j].

After calculating the sum for each subarray, we find its absolute value and compare it with a variable maxAbsSum that stores the maximum absolute sum found so far. If the current absolute sum is greater, we update maxAbsSum. The initial value of maxAbsSum is 0, which correctly handles the case of an empty subarray.

1class Solution {2    public int maxAbsoluteSum(int[] nums) {3        int maxAbsSum = 0;4        int n = nums.length;5        for (int i = 0; i < n; i++) {6            int currentSum = 0;7            for (int j = i; j < n; j++) {8                currentSum += nums[j];9                maxAbsSum = Math.max(maxAbsSum, Math.abs(currentSum));10            }11        }12        return maxAbsSum;13    }14}

Complexity

Time

O(n^2), where n is the number of elements in the input array. The nested loops lead to a quadratic number of operations.

Space

O(1), as we only use a constant amount of extra space for variables like `maxAbsSum` and `currentSum`.

Trade-offs

Pros

Simple to understand and implement.
It is a direct translation of the problem statement.

Cons

Inefficient for large inputs due to its quadratic time complexity.
Likely to cause a 'Time Limit Exceeded' error on competitive programming platforms for larger constraints.

A more efficient approach is based on the realization that the maximum absolute sum is the larger of two values: the maximum possible subarray sum and the absolute value of the minimum possible subarray sum. Both of these values can be computed in a single pass using Kadane's algorithm and its variation for the minimum sum.

Algorithm

Initialize maxSum = 0, currentMax = 0, minSum = 0, and currentMin = 0.
Iterate through each number num in the nums array.
To find the maximum subarray sum:
- Add num to currentMax.
- If currentMax becomes negative, reset it to 0.
- Update maxSum = max(maxSum, currentMax).
To find the minimum subarray sum:
- Add num to currentMin.
- If currentMin becomes positive, reset it to 0.
- Update minSum = min(minSum, currentMin).
After the loop, the result is max(maxSum, -minSum).

Walkthrough

The core idea is that max(abs(S)) for any subarray sum S is equivalent to max(max_subarray_sum, -min_subarray_sum). This transforms the problem into two separate, well-known problems: finding the maximum subarray sum and finding the minimum subarray sum.

Kadane's algorithm is a dynamic programming technique that solves the maximum subarray sum problem in linear time. We can adapt it to find the minimum subarray sum as well. We can perform both calculations in a single loop over the input array.

We maintain four variables:

currentMax: The maximum sum of a subarray ending at the current element.
maxSum: The overall maximum subarray sum found so far.
currentMin: The minimum sum of a subarray ending at the current element.
minSum: The overall minimum subarray sum found so far.

For each element, we update currentMax and currentMin. If currentMax drops below zero, we reset it to zero because a negative-sum prefix will not help in finding a larger positive sum. Similarly, if currentMin goes above zero, we reset it to zero as a positive-sum prefix won't help find a smaller negative sum. We continuously update the global maxSum and minSum.

Finally, the answer is max(maxSum, -minSum).

1class Solution {2    public int maxAbsoluteSum(int[] nums) {3        int maxSum = 0;4        int currentMax = 0;5        int minSum = 0;6        int currentMin = 0;7 8        for (int num : nums) {9            // Kadane's algorithm for maximum subarray sum10            currentMax += num;11            if (currentMax < 0) {12                currentMax = 0;13            }14            maxSum = Math.max(maxSum, currentMax);15 16            // Kadane's algorithm for minimum subarray sum17            currentMin += num;18            if (currentMin > 0) {19                currentMin = 0;20            }21            minSum = Math.min(minSum, currentMin);22        }23 24        return Math.max(maxSum, -minSum);25    }26}

Complexity

Time

O(n), where n is the number of elements in the array. This is because we only need a single pass through the array to compute both the maximum and minimum subarray sums.

Space

O(1), as it only requires a few variables to keep track of the current and overall sums, irrespective of the input size.

Trade-offs

Pros

Extremely efficient, with a linear time complexity.
Optimal solution for this problem.
Uses constant extra space.

Cons

The logic can be less intuitive than a straightforward brute-force approach, as it relies on the insight about maximum and minimum subarray sums.

Solutions

Solution

1class Solution { public int maxAbsoluteSum ( int [] nums ) { int f = 0 , g = 0 ; int ans = 0 ; for ( int x : nums ) { f = Math . max ( f , 0 ) + x ; g = Math . min ( g , 0 ) + x ; ans = Math . max ( ans , Math . max ( f , Math . abs ( g ))); } return ans ; } }

1class Solution {2public:3  int maxAbsoluteSum(vector<int> &nums) {4    int f = 0, g = 0;5    int ans = 0;6    for (int &x : nums) {7      f = max(f, 0) + x;8      g = min(g, 0) + x;9      ans = max({ans, f, abs(g)});10    }11    return ans;12  }13};

1class Solution : def maxAbsoluteSum ( self , nums : List [ int ]) -> int : f = g = 0 ans = 0 for x in nums : f = max ( f , 0 ) + x g = min ( g , 0 ) + x ans = max ( ans , f , abs ( g )) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem