1749. Maximum Absolute Sum of Any Subarray

dsadeck

Problem Statement

Maximum Absolute Sum of Any Subarray - LeetCode

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 x is a negative integer, then abs(x) = -x.
• If 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] <= 104

Pattern: Pattern Kadane’s Algorithm

---

Solution

 
// find both minSum and maxSum > return max(abs(min, max))
public static int maxAbsoluteSum (int[] nums){
	int minSum = Integer.MAX_VALUE, currMin = Integer.MAX_VALUE,
		maxSum = Integer.MIN_VALUE, currMax = Integer.MIN_VALUE;
	for (int num : nums) {
		if(currMin > 0) currMin = num;
		else currMin += num;
		
		if(currMax < 0) currMax = num;
		else currMax += num;
		
		// update max and min
		minSum = Math.min(currMin, minSum);
		maxSum = Math.max(currMax, maxSum);
	}
	return Math.max(Math.abs(minSum), maxSum);
}

Notes

• The questions will take the subarray that you give it and return the subarray with the greatest absolute sum i.e. Math.abs(sum)
  • This means that sum could be negative or positive.
  • So find the max positive sum subarray, and smallest negative subarray
  • See which has greater absolute value
  • Return absolute value
• Return the maximum absolute sum of any (possibly empty) subarray of nums.
  • This is an attempt at bait, since a non-empty subarray will be the largest always, under no circumstances will an empty subarray return the greatest absolute value. So don’t bother incorporating empty subarray logic into your code
    • If you are looking for minSum in a positive arrzay, it makes no sense to reset currMinsum to 0 if currMinsum > 0, since a positive currMinsum, will give a greater value, compared to 0 at the end, when supplied into the function
    • return Math.max(Math.abs(minSum), maxSum);