Skip to main content
Talentd

Maximum Absolute Sum of Any Subarray - Solution & Explanation

MediumArrayDynamic Programming18 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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.

 

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 <= 105
  • -104 <= nums[i] <= 104

Approach Overview

Problem Overview: You are given an integer array nums. A subarray can have a positive or negative sum. The task is to return the maximum possible absolute value of any subarray sum. In other words, you must consider both the largest positive subarray and the most negative subarray.

Approach 1: Modified Kadane's Algorithm (O(n) time, O(1) space)

This approach adapts the classic Kadane’s algorithm used for maximum subarray problems. Since the goal is the absolute sum, you track two running values while iterating through the array: the maximum subarray sum ending at the current index and the minimum subarray sum ending at the current index. The maximum captures large positive segments, while the minimum captures strongly negative segments. At each step you update both values using max(current, current + prevMax) and min(current, current + prevMin). The answer becomes max(abs(maxSum), abs(minSum)). This works because the largest magnitude subarray must be either the largest positive sum or the smallest negative sum. The algorithm scans the array once, making it O(n) time with constant O(1) extra space. This technique is a common extension of problems involving dynamic programming on arrays.

Approach 2: Prefix Sum with Minimum/Maximum Tracking (O(n) time, O(1) space)

Another way to view the problem is through prefix sums. Maintain a running prefix sum while traversing the array. The absolute sum of a subarray between indices i and j equals |prefix[j] - prefix[i]|. To maximize this value, you track the smallest and largest prefix sums seen so far. During each iteration, compute the current prefix sum and compare it with the stored minimum and maximum prefixes. The difference between the current prefix and those extremes represents the largest possible subarray ending at the current position. Update the result with max(abs(prefix - minPrefix), abs(prefix - maxPrefix)). Because you only store a few variables while scanning once, the complexity remains O(n) time and O(1) space. This interpretation is especially helpful when practicing prefix sum techniques and understanding range sum relationships in an array.

Recommended for interviews: The modified Kadane’s algorithm is usually the expected solution. It shows that you recognize the connection to the classic maximum subarray problem and can adapt it to track both positive and negative extremes. The prefix sum method demonstrates deeper understanding of how subarray sums relate to differences between cumulative sums, which interviewers also appreciate when discussing reasoning.

Approach 1: Modified Kadane's Algorithm

This approach involves modifying Kadane's algorithm to calculate not only the maximum subarray sum but also the minimum subarray sum. The idea is to maintain two running sums: one for the maximum subarray sum and one for the minimum subarray sum.

The maximum absolute sum will be the maximum of the absolute values of these two sums. While iterating through the array, update the maximum and minimum subarray sums by including the current element or starting anew from the current element.

This solution calculates both the maximum and minimum subarray sums while iterating through the array once. It keeps track of the maximum absolute value between the current maximum and minimum subarray sums in each iteration.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array, because we only make a single pass through the array.
Space Complexity: O(1), as we use a constant amount of extra space.

Try this approach in the editor →

Approach 2: Prefix Sum and Minimum/Maximum Tracking

This approach involves calculating the prefix sum of the array while simultaneously tracking the minimum and maximum prefix sums encountered. The maximum absolute sum of a subarray is then given by the largest absolute difference between any two prefix sums, effectively handled by keeping track of the minimum and maximum values of the running prefix sums. This approach leverages the fact that a subarray sum can be expressed as the difference between two prefix sums.

This solution calculates the running prefix sum and maintains the maximum and minimum prefix sums encountered. The maximum absolute sum is determined by the largest absolute difference between these values, which reflects the maximum absolute subarray sum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), with n as the number of array elements, since the array is processed in one loop.
Space Complexity: O(1), as the solution involves a constant number of variables.

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i] to represent the maximum value of the subarray ending with nums[i], and define g[i] to represent the minimum value of the subarray ending with nums[i]. Then the state transition equation of f[i] and g[i] is as follows:

$ \begin{aligned} f[i] &= max(f[i - 1], 0) + nums[i] \ g[i] &= min(g[i - 1], 0) + nums[i] \end{aligned}

The final answer is the maximum value of max(f[i], |g[i]|).

Since f[i] and g[i] are only related to f[i - 1] and g[i - 1], we can use two variables to replace the array, reducing the space complexity to O(1).

Time complexity O(n), space complexity O(1), where n is the length of the array nums$.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Modified Kadane's Algorithm

Time Complexity: O(n), where n is the number of elements in the array, because we only make a single pass through the array.
Space Complexity: O(1), as we use a constant amount of extra space.

Prefix Sum and Minimum/Maximum Tracking

Time Complexity: O(n), with n as the number of array elements, since the array is processed in one loop.
Space Complexity: O(1), as the solution involves a constant number of variables.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Modified Kadane's AlgorithmO(n)O(1)Best general solution. Ideal for interviews and large arrays.
Prefix Sum with Min/Max TrackingO(n)O(1)Useful when reasoning about prefix sums and subarray differences.

Video Solution

Maximum Absolute Sum of Any Subarray | Kadane's Algorithm | Leetcode 1749 | codestorywithMIK • codestorywithMIK • 17,305 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Absolute Sum of Any Subarray easy or hard?
Maximum Absolute Sum of Any Subarray is considered a Medium difficulty problem. The core logic is simple once you recognize that both maximum and minimum subarray sums must be tracked using a variation of Kadane’s algorithm.
Maximum Absolute Sum of Any Subarray Python/Java solution
Both Python and Java implementations typically follow the modified Kadane's algorithm pattern. Track current maximum and minimum subarray sums while iterating through the array, update the global result using their absolute values, and return the maximum magnitude found.
How to solve Maximum Absolute Sum of Any Subarray in O(n)?
Use a modified Kadane's algorithm. While iterating through the array, maintain the maximum subarray sum ending at the current index and the minimum subarray sum ending at the current index. Update the result using the maximum absolute value between those two running sums.
What is the best approach for Maximum Absolute Sum of Any Subarray?
Modified Kadane's algorithm is the most common solution. It tracks both the maximum subarray sum and the minimum subarray sum while scanning the array once. The answer is the larger absolute value between those two extremes, giving an O(n) time and O(1) space solution.
Is Maximum Absolute Sum of Any Subarray asked at Google/Amazon/Meta?
Variants of maximum subarray and prefix sum problems frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests understanding of Kadane’s algorithm and how to adapt it to track both positive and negative extremes.
What data structure is used in Maximum Absolute Sum of Any Subarray?
The problem mainly uses arrays with dynamic programming concepts. The solution keeps running sums while scanning the array, without requiring additional data structures beyond a few variables.
What is the time complexity of Maximum Absolute Sum of Any Subarray?
The optimal solution runs in O(n) time because the array is processed in a single pass. Only a few running variables are maintained, so the space complexity remains O(1).

Ready to solve this problem?

Practice Maximum Absolute Sum of Any Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Subarray