Problem

You are given an integer array nums. The absolute sum of a subarray [numsl, numsl+1, ..., numsr-1, numsr] is abs(numsl + numsl+1 + ... + numsr-1 + numsr).

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.

Examples

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^5
  • -10^4 <= nums[i] <= 10^4

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

Method 1 - Naive

  1. Use two loops to iterate through all possible subarrays.
  2. For each subarray, compute its sum.
  3. Calculate the absolute value of this sum using abs().
  4. Compare it to a variable (max_abs_sum) that keeps track of the maximum absolute sum and update it if necessary.

Pseudocode

max_abs_sum = 0

for start in range(len(nums)):
    for end in range(start, len(nums)):
        subarray_sum = 0
        for k in range(start, end + 1):
            subarray_sum += nums[k]

        max_abs_sum = max(max_abs_sum, abs(subarray_sum))

return max_abs_sum

Complexity

  • ⏰ Time complexity: O(n^3) due to 3 nested loops.
  • 🧺 Space complexity: O(1)

Method 2 - Using running sum

To optimise the naive ( O(n^3) ) approach, we avoid recalculating the subarray sum from scratch for each start to end pair. Instead:

  • Maintain a running sum during the inner loop.
  • Add the current element to the sum rather than recomputing it from the start.

Pseudocode

max_abs_sum = 0

for start in range(len(nums)):
    subarray_sum = 0
    for end in range(start, len(nums)):
        subarray_sum += nums[end]
        max_abs_sum = max(max_abs_sum, abs(subarray_sum))

return max_abs_sum

Complexity

  • ⏰ Time complexity: O(n^2) due to nested loops
  • 🧺 Space complexity: O(1)

Method 3 - Using prefix sum but naive

The prefix sum approach is a way to optimise subarray sums by precomputing cumulative sums for the array. Once we have the prefix sums, the sum of any subarray between indices i and j can be computed in O(1), which avoids redundant calculations. $$ \text{subarraySum} = \text{prefixSum}[j+1] - \text{prefixSum}[i] $$

Here is the approach:

  1. Compute the prefix_sum array in ( O(n) ).
  2. Use two nested loops:
    • Outer loop: Fix a starting index for the subarray (i).
    • Inner loop: Compute all subarray sums starting from i by using the prefix_sum array.
    • Take the absolute value of each subarray sum and track the maximum.

Pseudocode

prefix_sum = [0] * (len(nums) + 1)
for i in range(len(nums)):
    prefix_sum[i+1] = prefix_sum[i] + nums[i]

max_abs_sum = 0

for start in range(len(nums)):
    for end in range(start, len(nums)):
        subarray_sum = prefix_sum[end + 1] - prefix_sum[start]
        max_abs_sum = max(max_abs_sum, abs(subarray_sum))

return max_abs_sum

Complexity

  • ⏰ Time complexity: O(n^2) due to nested loops
  • 🧺 Space complexity: O(1)

Method 4 - Using prefix sum but optimal

Instead of explicitly checking all subarray sums:

  1. Maintain the current prefix sum while iterating through the array.
  2. Track two key values:
    • The minimum prefix sum encountered so far (minPrefixSum).
    • The maximum prefix sum encountered so far (maxPrefixSum).
  3. At each step, the absolute sum is maximised by:
    • Subtracting the minimum prefix sum from the current prefix sum (positive subarrays).
    • Subtracting the current prefix sum from the maximum prefix sum (negative subarrays).
  4. The absolute maximum subarray sum will be the absolute difference between maxPrefixSum and minPrefixSum.

Code

Java
class Solution {
    public int maxAbsoluteSum(int[] nums) {
        // Initialize prefix sum, minPrefixSum, and maxPrefixSum
        int prefixSum = 0;
        int minPrefixSum = 0;
        int maxPrefixSum = 0;

        // Iterate through the array
        for (int num : nums) {
            // Update the running prefix sum
            prefixSum += num;

            // Update the minimum and maximum prefix sums encountered so far
            minPrefixSum = Math.min(minPrefixSum, prefixSum);
            maxPrefixSum = Math.max(maxPrefixSum, prefixSum);
        }

        // Return the absolute difference between maximum and minimum prefix sums
        return maxPrefixSum - minPrefixSum;
    }
}
Python
class Solution:
    def maxAbsoluteSum(self, nums: list[int]) -> int:
        # Initialize prefix sum, minPrefixSum, and maxPrefixSum
        prefix_sum = 0
        min_prefix_sum = 0
        max_prefix_sum = 0

        # Iterate through the array
        for num in nums:
            # Update the running prefix sum
            prefix_sum += num

            # Update the minimum and maximum prefix sums encountered so far
            min_prefix_sum = min(min_prefix_sum, prefix_sum)
            max_prefix_sum = max(max_prefix_sum, prefix_sum)

        # Return the absolute difference between maximum and minimum prefix sums
        return max_prefix_sum - min_prefix_sum

Complexity

  • ⏰ Time complexity: O(n), due to single iteration through the array.
  • 🧺 Space complexity: O(1). Only a few variables are used for tracking.

Method 5 - Kadane’s algorithm

The absolute sum can be derived using abs() of the subarray sum, but instead of calculating the absolute sum for every subarray (which involves nested loops and would be inefficient), we can decompose the problem into two related tasks: 1. Find the maximum subarray sum (Kadane’s Algorithm). 2. Find the minimum subarray sum (Kadane’s Algorithm on -nums).

Kadane’s Algorithm gives the maximum sum of any contiguous subarray in linear time. By negating the array, it can also be used to find the smallest sum of any contiguous subarray.

For Kadane’s approach refer here: Kadane’s Algorithm for Maximum Subarray Sum

Approach

  • Calculate the maximum subarray sum using Kadane’s Algorithm.
  • Calculate the minimum subarray sum using Kadane’s Algorithm with the array negated, which effectively gives the smallest subarray sum.
  • The result is the maximum of the absolute values of the maximum and minimum subarray sums.

Code

Java
class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int maxSum = 0, minSum = 0, maxCurr = 0, minCurr = 0;
        
        for (int num : nums) {
            // Kadane's for max sum
            maxCurr = Math.max(num, maxCurr + num);
            maxSum = Math.max(maxSum, maxCurr);
            
            // Kadane's for min sum
            minCurr = Math.min(num, minCurr + num);
            minSum = Math.min(minSum, minCurr);
        }
        
        // Return the maximum absolute sum
        return Math.max(maxSum, Math.abs(minSum));
    }
}
Python
class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        max_sum, min_sum = 0, 0
        max_curr, min_curr = 0, 0 
        
        for num in nums:
            # Kadane's for max sum
            max_curr = max(num, max_curr + num)
            max_sum = max(max_sum, max_curr)
            
            # Kadane's for min sum
            min_curr = min(num, min_curr + num)
            min_sum = min(min_sum, min_curr)
        
        # Return the maximum absolute sum
        return max(max_sum, abs(min_sum))

Complexity

  • ⏰ Time complexity:  O(n) because Kadane’s Algorithm runs in linear time.
  • 🧺 Space complexity: O(1) as the algorithm only uses a few variables to store intermediate results.