【每日一题Day289】LC1749任意子数组和的绝对值的最大值 | dp

任意子数组和的绝对值的最大值【LC1749】

给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的绝对值 为abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。

请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。

abs(x) 定义如下：

• 如果 x 是负整数，那么 abs(x) = -x 。
• 如果 x 是非负整数，那么 abs(x) = x 。

和这两题很像，都是通过前面两种不同的状态转移过来的，删除一次得到子数组最大和&访问数组中的位置使分数最大

• 思路：dp

• 由于所求为子数组和的绝对值，某个子数组和nums[0,i-1]可能为负数或者正数，如果
  

• nums[i]与前一子数组的正负值相同，那么取绝对值后的结果将增大。因此需要记录以nums[i]结尾的最小负数和以及最大正数和
  

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int res = 0, neg = 0, pos = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++){            
            neg = Math.min(0, neg + nums[i]);// 以nums[i]结尾的和为负数的子数组和
            pos = Math.max(0, pos + nums[i]);// 以nums[i]结尾的和为正数的子数组和
            res = Math.max(res, Math.max(-neg, pos));
        }
        return res;
    }
}