#1749
Maximum Absolute Sum of Any Subarray
Medium Kadane max & min
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the largest absolute value of any subarray sum (an empty subarray counts as 0).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the largest |sum| of any piece.
Why this works: the largest absolute value is either the most positive sum or the most negative sum; run Kadane for both.
Example: [1, -3, 2, 3, -4]
best positive: 2 + 3 = 5most negative: -4answer 5
✦Hints open one at a time
The largest absolute sum is either the biggest positive sum or the most negative sum.
Run Kadane for both at once.
↗Approach
Track the max-ending-here and min-ending-here sums (both allowed to reset to 0). The answer is max(bestMax, −bestMin).
</>Solution (Java)
class Solution {
public int maxAbsoluteSum(int[] nums) {
int curMax = 0, curMin = 0, best = 0;
for (int x : nums) {
curMax = Math.max(0, curMax + x);
curMin = Math.min(0, curMin + x);
best = Math.max(best, Math.max(curMax, -curMin));
}
return best;
}
}!Common mistake
Taking the absolute value of each element first — that changes the problem.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Kadane, Dutch Flag & Moore's Voting
🎬 Episodes 11–13: video coming soon