Skip to content

1749. Maximum Absolute Sum of Any Subarray

Description

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

Solutions

Solution 1: Dynamic Programming

Thinking

The maximum absolute subarray sum is the larger of the maximum subarray sum and the absolute minimum subarray sum.

Kadane tracks the best and worst sums \(f,g\) ending here; the answer is the global max of \(f\) and \(|g|\).

We define \(f[i]\) to represent the maximum value of the subarray ending with \(nums[i]\), and define \(g[i]\) to represent the minimum value of the subarray ending with \(nums[i]\). Then the state transition equation of \(f[i]\) and \(g[i]\) is as follows:

\[ \begin{aligned} f[i] &= \max(f[i - 1], 0) + nums[i] \\ g[i] &= \min(g[i - 1], 0) + nums[i] \end{aligned} \]

The final answer is the maximum value of \(max(f[i], |g[i]|)\).

Since \(f[i]\) and \(g[i]\) are only related to \(f[i - 1]\) and \(g[i - 1]\), we can use two variables to replace the array, reducing the space complexity to \(O(1)\).

Time complexity \(O(n)\), space complexity \(O(1)\), where \(n\) is the length of the array \(nums\).

1
2
3
4
5
6
7
8
9
class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        f = g = 0
        ans = 0
        for x in nums:
            f = max(f, 0) + x
            g = min(g, 0) + x
            ans = max(ans, f, abs(g))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int f = 0, g = 0;
        int ans = 0;
        for (int x : nums) {
            f = Math.max(f, 0) + x;
            g = Math.min(g, 0) + x;
            ans = Math.max(ans, Math.max(f, Math.abs(g)));
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int f = 0, g = 0;
        int ans = 0;
        for (int& x : nums) {
            f = max(f, 0) + x;
            g = min(g, 0) + x;
            ans = max({ans, f, abs(g)});
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func maxAbsoluteSum(nums []int) (ans int) {
    var f, g int
    for _, x := range nums {
        f = max(f, 0) + x
        g = min(g, 0) + x
        ans = max(ans, max(f, abs(g)))
    }
    return
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function maxAbsoluteSum(nums: number[]): number {
    let f = 0;
    let g = 0;
    let ans = 0;
    for (const x of nums) {
        f = Math.max(f, 0) + x;
        g = Math.min(g, 0) + x;
        ans = Math.max(ans, f, -g);
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn max_absolute_sum(nums: Vec<i32>) -> i32 {
        let mut f = 0;
        let mut g = 0;
        let mut ans = 0;
        for x in nums {
            f = i32::max(f, 0) + x;
            g = i32::min(g, 0) + x;
            ans = i32::max(ans, f.max(-g));
        }
        ans
    }
}

Comments