1749. Maximum Absolute Sum of Any Subarray - Detailed Explanation
Problem Statement
You are given an integer array nums. A subarray is a contiguous part of the array, and its sum is the sum of all the elements within it. The absolute sum of a subarray is defined as the absolute value of its sum. Your task is to find and return the maximum absolute sum among all possible subarrays of nums.
For example, if a subarray has a sum of -5, its absolute sum is 5. You need to maximize this absolute sum over every possible subarray.
Examples
-
Example 1:
- Input:
nums = [1, -3, 2, 3, -4] - Output:
5 - Explanation:
- Compute prefix sums:
P[0] = 0
P[1] = 1
P[2] = 1 + (-3) = -2
P[3] = -2 + 2 = 0
P[4] = 0 + 3 = 3
P[5] = 3 + (-4) = -1 - The maximum prefix sum is 3 and the minimum prefix sum is -2.
- The maximum absolute sum of any subarray is
3 - (-2) = 5.
- Compute prefix sums:
- Input:
-
Example 2:
- Input:
nums = [2, -5, 1, -4, 3, 0] - Output: (Example analysis not provided, but the approach is the same)
- Input:
Key Insights and Hints
-
Using Prefix Sums:
A subarray sum from index i to j can be expressed as the difference between two prefix sums:
[ \text{sum}[i \ldots j] = \text{prefix}[j+1] - \text{prefix}[i] ] -
Maximizing the Difference:
To maximize the absolute value of any subarray sum, you need to maximize the difference between any two prefix sums. In particular, the maximum absolute sum equals: [ \text{maxAbsSum} = \max(\text{prefix}) - \min(\text{prefix}) ] This works because the largest difference between any two prefix sums yields the maximum possible subarray sum in absolute value. -
Optimal Approach:
You can compute the prefix sum while tracking the minimum and maximum values seen so far. The final answer is the difference between these two values.
Approaches to Solve the Problem
Approach: One-Pass with Prefix Sum Tracking
-
Initialize Variables:
- Set a variable
prefixto 0 (to represent the current prefix sum). - Set
minPrefixto 0 andmaxPrefixto 0.
- Set a variable
-
Iterate Through the Array:
- For each number in nums, update the current prefix sum.
- Update
minPrefixif the current prefix sum is smaller. - Update
maxPrefixif the current prefix sum is larger.
-
Calculate the Answer:
- The answer is the difference
maxPrefix - minPrefix, which is the maximum absolute sum of any subarray.
- The answer is the difference
Code Implementations
Python Implementation
Java Implementation
Complexity Analysis
-
Time Complexity: O(n)
We make a single pass through the array to compute the prefix sums and update the minimum and maximum seen. -
Space Complexity: O(1)
Only a constant amount of extra space is used (for the prefix sum, minPrefix, and maxPrefix variables).
Step-by-Step Walkthrough
-
Initialization:
prefix = 0,minPrefix = 0,maxPrefix = 0.
-
Processing Each Element:
- For each number in nums:
- Update
prefixby adding the current number. - Compare
prefixwithminPrefixandmaxPrefixto update them accordingly.
- Update
- For example, with
nums = [1, -3, 2, 3, -4]:- After processing
1:prefix = 1,minPrefix = 0,maxPrefix = 1 - After
-3:prefix = -2,minPrefix = -2,maxPrefix = 1 - After
2:prefix = 0,minPrefix = -2,maxPrefix = 1 - After
3:prefix = 3,minPrefix = -2,maxPrefix = 3 - After
-4:prefix = -1,minPrefix = -2,maxPrefix = 3
- After processing
- For each number in nums:
-
Compute the Final Answer:
- The maximum absolute subarray sum is
maxPrefix - minPrefix = 3 - (-2) = 5.
- The maximum absolute subarray sum is
Common Pitfalls & Edge Cases
-
Edge Case: Empty Array
While the problem constraints guarantee that nums is non-empty, if it were empty, the answer should be 0. -
Edge Case: All Positive or All Negative Numbers
-
If all numbers are positive, the maximum prefix will be the sum of the entire array and the minimum prefix remains 0.
-
If all numbers are negative, the minimum prefix will be the sum of the entire array and the maximum prefix will be 0. In both cases, the formula
maxPrefix - minPrefixstill correctly computes the maximum absolute sum.
-
-
Pitfall: Not Using Absolute Value Directly
Instead of trying to compute absolute values of every subarray sum (which would be inefficient), note that the maximum difference between any two prefix sums directly yields the result.
Alternative Variations and Related Problems
-
Alternative Variation:
Problems that ask for the maximum sum of any subarray (e.g., "Maximum Subarray" / Kadane’s Algorithm) are related, although they do not require taking the absolute value. -
Related Problems for Further Practice:
- Maximum Subarray (Kadane’s Algorithm): Find the subarray with the maximum sum.
- Subarray Sum Problems: Many problems involve computing sums over subarrays, which can often be solved using prefix sums.
GET YOUR FREE
Coding Questions Catalog
