1849. Maximum Absolute Sum Of Any Subarray¶

Difficulty: Medium

1849. Maximum Absolute Sum of Any Subarray

Medium

You are given an integer array nums. The absolute sum of a subarray [nums_l, nums_l+1, ..., nums_r-1, nums_r] is abs(nums_l + nums_l+1 + ... + nums_r-1 + nums_r).

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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Solution¶

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n = nums.length;
        int maxi = 0;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < 0) {
                maxi = Math.max(maxi, sum);
                if (sum + nums[i] < 0) sum = 0;
                else {
                    sum += nums[i];
                    maxi = Math.max(maxi, sum);
                }
            }
            else sum += nums[i];
        }
        if (sum > 0) maxi = Math.max(maxi, sum);
        sum = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                maxi = Math.max(maxi, sum);
                if (sum - nums[i] < 0) sum = 0; 
                else {
                    sum -= nums[i];
                    maxi = Math.max(maxi, sum);
                }
            }
            else sum += Math.abs(nums[i]);
        }
        if (sum > 0) maxi = Math.max(maxi, sum);
        return maxi;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here