1749. Maximum Absolute Sum of Any Subarray

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

1749. Maximum Absolute Sum of Any Subarray
struct Solution;

impl Solution {
    fn max_absolute_sum(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut sum = 0;
        let mut min = 0;
        let mut max = 0;
        let mut sub_min = 0;
        let mut sub_max = 0;
        let mut res = 0;
        for i in 0..n {
            sum += nums[i];
            min = min.min(sum);
            max = max.max(sum);
            sub_max = sub_max.max(sum - min);
            sub_min = sub_min.min(sum - max);
            res = res.max(sub_max.abs());
            res = res.max(sub_min.abs());
        }
        res
    }
}

#[test]
fn test() {
    let nums = vec![1, -3, 2, 3, -4];
    let res = 5;
    assert_eq!(Solution::max_absolute_sum(nums), res);
    let nums = vec![2, -5, 1, -4, 3, -2];
    let res = 8;
    assert_eq!(Solution::max_absolute_sum(nums), res);
}