Solution to Leetcode 1749. Maximum Absolute Sum of Any Subarray

This problem is very classic. I find it helpful to see all the values in the array, as differences between values in a series, and to draw it on paper. Don’t try to find a complicated solution to this problem. You only need to remember a couple of things like the minimum and maximum sum you encountered for instance. Try to do it in one simple pass.

We apply a simple greedy method to find the maximum absolute sum of any subarray.

As we traverse the array, we keep track of the current sum.

We retain the max_sum and the min_sum that we encountered.

Each time, we compare current with the max_sum and min_sum, the difference is the maximum sum of subarrays ending with the index i, and the maximum negative sum for all subarrays ending with the index i.

We remember max which is the current max absolute sum of any subarray that was encountered yet.

Full solution in Java:

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int current = 0;
        int max_sum = 0;
        int min_sum = 0;
        int max = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            current += nums[i];
            if (current > max_sum) {
                max_sum = current;
            }
            if (current < min_sum) {
                min_sum = current;
            }
            int a = current - min_sum;
            int b = max_sum - current;
            int c = Math.max(a, b);
            if (c > max) {
                max = c;
            }
        }
        return max;
    }
}

Happy coding!

I am tutoring, feel free to contact me poitevinpm@gmail.com