AlgoMaster Logo

Maximum Absolute Sum of Any Subarray

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We need to find a contiguous subarray whose sum has the largest absolute value. That means we care about both the maximum positive sum and the minimum negative sum (most negative), because taking the absolute value of a very negative sum could give us a larger result than the maximum positive sum.

For example, if the maximum subarray sum is 5 but the minimum subarray sum is -8, then the maximum absolute sum is 8, not 5. So this problem is really asking: find both the maximum subarray sum and the minimum subarray sum, then return whichever has a larger absolute value.

This is a twist on the classic Maximum Subarray problem (Kadane's algorithm). Instead of just tracking the maximum, we need to track the minimum too.

Key Constraints:

  • 1 <= nums.length <= 10^5: With n up to 100,000, we need an O(n log n) solution or better. An O(n^2) brute force checking all subarrays would be 10 billion operations, which is too slow.
  • -10^4 <= nums[i] <= 10^4: Values are bounded, so the maximum possible subarray sum is 10^5 * 10^4 = 10^9, which fits in a 32-bit integer. No overflow concerns in most languages.

Approach 1: Brute Force

Intuition

Check every possible subarray, compute its sum, take the absolute value, and track the maximum. For each starting index, extend the subarray one element at a time and keep a running sum so each new sum is computed in O(1) from the previous one.

Algorithm

  1. Initialize maxAbsSum = 0.
  2. For each starting index i from 0 to n-1, initialize currentSum = 0.
  3. For each ending index j from i to n-1, add nums[j] to currentSum.
  4. Update maxAbsSum = max(maxAbsSum, abs(currentSum)).
  5. Return maxAbsSum.

Visualization and Code

Loading animation...

The brute force checks every subarray, which is too slow for n up to 10^5. Both the maximum and minimum subarray sums can be found in a single linear pass instead.

Approach 2: Kadane's Algorithm

Intuition

The maximum absolute subarray sum is either the maximum subarray sum or the absolute value of the minimum subarray sum, whichever is larger. abs(sum) is large when sum is far from zero in either direction, so we need both extremes.

Kadane's algorithm finds the maximum subarray sum in O(n) by maintaining a running sum and starting a fresh subarray whenever the running sum drops below the current element (a negative prefix only lowers future sums). The same algorithm with the comparisons flipped tracks the minimum subarray sum. Both run in the same single pass.

Algorithm

  1. Initialize maxSum = 0, minSum = 0, currentMax = 0, currentMin = 0.
  2. For each element in the array:
    • Update currentMax = max(num, currentMax + num) (standard Kadane's).
    • Update maxSum = max(maxSum, currentMax).
    • Update currentMin = min(num, currentMin + num) (inverted Kadane's).
    • Update minSum = min(minSum, currentMin).
  3. Return max(maxSum, abs(minSum)).

Visualization and Code

Loading animation...

Kadane's is already optimal. A prefix-sum view of the same problem reaches the answer through a different argument and shorter code.

Approach 3: Prefix Sum

Intuition

The sum of subarray nums[l..r] equals prefix[r+1] - prefix[l], where prefix[i] is the sum of the first i elements. So the maximum absolute subarray sum is the maximum value of abs(prefix[j] - prefix[i]) over all valid pairs where j > i.

To maximize abs(prefix[j] - prefix[i]), we want the largest possible gap between any two prefix sums. That gap is max(prefix) - min(prefix). There is no need to store the entire prefix sum array: we track the running prefix sum and keep the maximum and minimum values seen so far.

Algorithm

  1. Initialize prefixSum = 0, maxPrefix = 0, minPrefix = 0.
  2. For each element in the array, add it to prefixSum.
  3. Update maxPrefix = max(maxPrefix, prefixSum).
  4. Update minPrefix = min(minPrefix, prefixSum).
  5. Return maxPrefix - minPrefix.

Visualization and Code

Loading animation...