Maximum Absolute Sum of Any Subarray solution and explanation
Google
9 more videos on this problem
Maximum Absolute Sum of Any Subarray | Kadane's Algorithm | Leetcode 1749 | codestorywithMIKcodestorywithMIK · 30:50 · 17K views
Maximum Absolute Sum of Any Subarray - Leetcode 1749 - PythonNeetCodeIO · 17:18 · 10K views
Maximum Absolute Sum of Any Subarray | Leetcode 1749Techdose · 12:43 · 4K views
1749. Maximum Absolute Sum of Any Subarray | Prefix Sums | 2 ApproachesAryan Mittal · 19:36 · 1K views
1749. Maximum Absolute Sum of Any Subarray | leetcode daily challenge | greedy | faang | shashcodeShashCode · 16:17 · 1K views
Maximum absolute sum of any subarray | dynamic programming | Leetcode#1749Joey'sTech · 7:39 · 1K views
1749. Maximum Absolute Sum of Any Subarray (Leetcode Medium)Programming Live with Larry · 7:12 · 901 views
LeetCode 1749 Maximum Absolute Sum of Any Subarray | Kadane's AlgorithmCode Harmony · 17:56 · 817 views
LeetCode 1749 Maximum Absolute Sum of Any Subarray - Java Solution Using Kadane's AlgorithmAlgorithmicIQ · 14:13 · 337 views
Leetcode 1749. Maximum Absolute Sum of Any SubarrayElite Code · 16:16 · 265 views
The 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
xis a negative integer, thenabs(x) = -x. - If
xis a non-negative integer, thenabs(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.
def max_absolute_sum(nums):
max_sum = 0
min_sum = 0
max_absolute = 0
for num in nums:
max_sum = max(num, max_sum + num)
min_sum = min(num, min_sum + num)
max_absolute = max(max_absolute, max(max_sum, -min_sum))
return max_absolute
nums = [1, -3, 2, 3, -4]
print("Max Absolute Sum:", max_absolute_sum(nums))public class MaxAbsoluteSum {
public static int maxAbsoluteSum(int[] nums) {
int maxSum = 0, minSum = 0, maxAbsolute = 0;
for (int num : nums) {
maxSum = Math.max(num, maxSum + num);
minSum = Math.min(num, minSum + num);
maxAbsolute = Math.max(maxAbsolute, Math.max(maxSum, -minSum));
}
return maxAbsolute;
}
public static void main(String[] args) {
int[] nums = {1, -3, 2, 3, -4};
System.out.println("Max Absolute Sum: " + maxAbsoluteSum(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxAbsoluteSum(vector<int>& nums) {
int max_sum = 0, min_sum = 0, max_absolute = 0;
for (int num : nums) {
max_sum = max(num, max_sum + num);
min_sum = min(num, min_sum + num);
max_absolute = max(max_absolute, max(max_sum, -min_sum));
}
return max_absolute;
}
int main() {
vector<int> nums = {1, -3, 2, 3, -4};
cout << "Max Absolute Sum: " << maxAbsoluteSum(nums) << endl;
return 0;
}function maxAbsoluteSum(nums) {
let maxSum = 0, minSum = 0, maxAbsolute = 0;
for (let num of nums) {
maxSum = Math.max(num, maxSum + num);
minSum = Math.min(num, minSum + num);
maxAbsolute = Math.max(maxAbsolute, Math.max(maxSum, -minSum));
}
return maxAbsolute;
}
const nums = [1, -3, 2, 3, -4];
console.log("Max Absolute Sum:", maxAbsoluteSum(nums));#include <stdio.h>
#include <stdlib.h>
int maxAbsoluteSum(int* nums, int numsSize) {
int max_sum = 0, min_sum = 0, max_absolute = 0;
for (int i = 0; i < numsSize; ++i) {
max_sum = max_sum > 0 ? max_sum + nums[i] : nums[i];
min_sum = min_sum < 0 ? min_sum + nums[i] : nums[i];
if (max_sum > max_absolute) {
max_absolute = max_sum;
}
if (-min_sum > max_absolute) {
max_absolute = -min_sum;
}
}
return max_absolute;
}
int main() {
int nums[] = {1, -3, 2, 3, -4};
int result = maxAbsoluteSum(nums, 5);
printf("Max Absolute Sum: %d\n", result);
return 0;
}using System;
class Program {
static int MaxAbsoluteSum(int[] nums) {
int maxSum = 0, minSum = 0, maxAbsolute = 0;
foreach (var num in nums) {
maxSum = Math.Max(num, maxSum + num);
minSum = Math.Min(num, minSum + num);
maxAbsolute = Math.Max(maxAbsolute, Math.Max(maxSum, -minSum));
}
return maxAbsolute;
}
static void Main() {
int[] nums = {1, -3, 2, 3, -4};
Console.WriteLine("Max Absolute Sum: " + MaxAbsoluteSum(nums));
}
}The Python solution makes use of max and min functions to dynamically update the subarray sums. The approach is concise and efficient.
Time Complexity: O(n), where n is the number of items in nums.
Space Complexity: O(1), as no additional data structures are used except for variables.
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.
def max_absolute_sum(nums):
prefix_sum = 0
max_prefix = 0
min_prefix = 0
max_abs = 0
for num in nums:
prefix_sum += num
max_prefix = max(max_prefix, prefix_sum)
min_prefix = min(min_prefix, prefix_sum)
max_abs = max(max_abs, abs(max_prefix - min_prefix))
return max_abs
nums = [2, -5, 1, -4, 3, -2]
print("Max Absolute Sum:", max_absolute_sum(nums))public class MaxAbsoluteSumPrefix {
public static int maxAbsoluteSum(int[] nums) {
int prefixSum = 0;
int maxPrefix = 0, minPrefix = 0;
int maxAbs = 0;
for (int num : nums) {
prefixSum += num;
maxPrefix = Math.max(maxPrefix, prefixSum);
minPrefix = Math.min(minPrefix, prefixSum);
maxAbs = Math.max(maxAbs, Math.abs(maxPrefix - minPrefix));
}
return maxAbs;
}
public static void main(String[] args) {
int[] nums = {2, -5, 1, -4, 3, -2};
System.out.println("Max Absolute Sum: " + maxAbsoluteSum(nums));
}
}#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int maxAbsoluteSum(vector<int>& nums) {
int prefix_sum = 0;
int max_prefix = 0, min_prefix = 0;
int max_abs = 0;
for (int num : nums) {
prefix_sum += num;
max_prefix = max(max_prefix, prefix_sum);
min_prefix = min(min_prefix, prefix_sum);
max_abs = max(max_abs, abs(max_prefix - min_prefix));
}
return max_abs;
}
int main() {
vector<int> nums = {2, -5, 1, -4, 3, -2};
cout << "Max Absolute Sum: " << maxAbsoluteSum(nums) << endl;
return 0;
}function maxAbsoluteSum(nums) {
let prefixSum = 0;
let maxPrefix = 0, minPrefix = 0;
let maxAbs = 0;
for (let num of nums) {
prefixSum += num;
maxPrefix = Math.max(maxPrefix, prefixSum);
minPrefix = Math.min(minPrefix, prefixSum);
maxAbs = Math.max(maxAbs, Math.abs(maxPrefix - minPrefix));
}
return maxAbs;
}
const nums = [2, -5, 1, -4, 3, -2];
console.log("Max Absolute Sum:", maxAbsoluteSum(nums));#include <stdio.h>
#include <stdlib.h>
int maxAbsoluteSum(int* nums, int numsSize) {
int prefix_sum = 0;
int max_prefix = 0, min_prefix = 0;
int max_abs = 0;
for (int i = 0; i < numsSize; ++i) {
prefix_sum += nums[i];
if (prefix_sum > max_prefix) {
max_prefix = prefix_sum;
}
if (prefix_sum < min_prefix) {
min_prefix = prefix_sum;
}
int current_max_abs = abs(max_prefix - min_prefix);
if (current_max_abs > max_abs) {
max_abs = current_max_abs;
}
}
return max_abs;
}
int main() {
int nums[] = {2, -5, 1, -4, 3, -2};
int result = maxAbsoluteSum(nums, 6);
printf("Max Absolute Sum: %d\n", result);
return 0;
}using System;
class Program {
static int MaxAbsoluteSum(int[] nums) {
int prefixSum = 0;
int maxPrefix = 0, minPrefix = 0, maxAbs = 0;
foreach (int num in nums) {
prefixSum += num;
maxPrefix = Math.Max(maxPrefix, prefixSum);
minPrefix = Math.Min(minPrefix, prefixSum);
maxAbs = Math.Max(maxAbs, Math.Abs(maxPrefix - minPrefix));
}
return maxAbs;
}
static void Main() {
int[] nums = {2, -5, 1, -4, 3, -2};
Console.WriteLine("Max Absolute Sum: " + MaxAbsoluteSum(nums));
}
}The Python code computes the prefix sum and tracks the minimum and maximum prefixes, using their difference to calculate the maximum absolute sum efficiently.
Time Complexity: O(n), where n is the size of the list.
Space Complexity: O(1), due to constant use of extra space.
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$.
function maxAbsoluteSum(nums: number[]): number {
let f = 0;
let g = 0;
let ans = 0;
for (const x of nums) {
f = Math.max(f, 0) + x;
g = Math.min(g, 0) + x;
ans = Math.max(ans, f, -g);
}
return ans;
}func maxAbsoluteSum(nums []int) (ans int) {
var f, g int
for _, x := range nums {
f = max(f, 0) + x
g = min(g, 0) + x
ans = max(ans, max(f, abs(g)))
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn max_absolute_sum(nums: Vec<i32>) -> i32 {
let mut f = 0;
let mut g = 0;
let mut ans = 0;
for x in nums {
f = i32::max(f, 0) + x;
g = i32::min(g, 0) + x;
ans = i32::max(ans, f.max(-g));
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Modified Kadane's Algorithm | Time Complexity: O(n), where n is the number of items in |
| Prefix Sum and Minimum/Maximum Tracking | Time Complexity: O(n), where n is the size of the list. |
| Dynamic Programming | – |
Complexity analysis
| 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. |
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).