Maximum Absolute Sum of Any Subarray
Problem
Given an integer array nums, the absolute sum of a subarray is the absolute value of the sum of its elements. Return the maximum absolute sum over all (possibly empty) subarrays. Since the empty subarray sums to 0, the answer is never negative.
nums = [1,-3,2,3,-4]5nums = [2,-5,1,-4,3,-2]8def maxAbsoluteSum(nums):
max_sum = min_sum = 0
cur_max = cur_min = 0
for x in nums:
cur_max = max(cur_max + x, 0)
cur_min = min(cur_min + x, 0)
max_sum = max(max_sum, cur_max)
min_sum = min(min_sum, cur_min)
return max(max_sum, -min_sum)function maxAbsoluteSum(nums) {
let maxSum = 0, minSum = 0;
let curMax = 0, curMin = 0;
for (const x of nums) {
curMax = Math.max(curMax + x, 0);
curMin = Math.min(curMin + x, 0);
maxSum = Math.max(maxSum, curMax);
minSum = Math.min(minSum, curMin);
}
return Math.max(maxSum, -minSum);
}int maxAbsoluteSum(int[] nums) {
int maxSum = 0, minSum = 0;
int curMax = 0, curMin = 0;
for (int x : nums) {
curMax = Math.max(curMax + x, 0);
curMin = Math.min(curMin + x, 0);
maxSum = Math.max(maxSum, curMax);
minSum = Math.min(minSum, curMin);
}
return Math.max(maxSum, -minSum);
}int maxAbsoluteSum(vector<int>& nums) {
int maxSum = 0, minSum = 0;
int curMax = 0, curMin = 0;
for (int x : nums) {
curMax = max(curMax + x, 0);
curMin = min(curMin + x, 0);
maxSum = max(maxSum, curMax);
minSum = min(minSum, curMin);
}
return max(maxSum, -minSum);
}Explanation
The maximum absolute sum is either a very large positive subarray sum or a very negative one (whose absolute value is large). So we look for both extremes in a single pass.
This is Kadane's algorithm run twice at once. We keep two running sums: cur_max is the best subarray sum ending at the current element, and cur_min is the worst (most negative) subarray sum ending here.
For each value x we extend or restart: cur_max = max(cur_max + x, 0). Clamping to 0 represents dropping the prefix and choosing the empty subarray, which is allowed. Symmetrically cur_min = min(cur_min + x, 0).
After updating the running sums we fold them into the global best and worst: max_sum = max(max_sum, cur_max) and min_sum = min(min_sum, cur_min).
The answer is max(max_sum, -min_sum): the larger of the biggest positive sum and the magnitude of the most negative sum. Everything starts at 0, so an all-positive or all-negative array still works, and the empty subarray (value 0) is the floor.