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:
x is a negative integer, then abs(x) = -x.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] <= 104Problem 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.
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.
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.
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.
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.
| Approach | Complexity |
|---|---|
| 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. |
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Modified Kadane's Algorithm | O(n) | O(1) | Best general solution. Ideal for interviews and large arrays. |
| Prefix Sum with Min/Max Tracking | O(n) | O(1) | Useful when reasoning about prefix sums and subarray differences. |
Maximum Absolute Sum of Any Subarray | Kadane's Algorithm | Leetcode 1749 | codestorywithMIK • codestorywithMIK • 14,805 views views
Watch 9 more video solutions →Practice Maximum Absolute Sum of Any Subarray with our built-in code editor and test cases.
Practice on FleetCode