2021-03-06 1749. 任意子数组和的绝对值的最大值

题目地址

https://leetcode-cn.com/problems/maximum-absolute-sum-of-any-subarray/

题目描述

给你一个整数数组 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 。
 
示例 1：
输入：nums = [1,-3,2,3,-4]
输出：5
解释：子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5 。
示例 2：
输入：nums = [2,-5,1,-4,3,-2]
输出：8
解释：子数组 [-5,1,-4] 和的绝对值最大，为 abs(-5+1-4) = abs(-8) = 8 。
 
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104

思路

前缀和法，sum[i]表示i往前数的和，再去遍历这个前缀和的列表，看前面截去多少会使和的绝对值最大。如果和为正，截去前面的最小的才可能是最大，如果和为负，截去最大的可能使和最大。
PS：最开始也想用滑动窗口法，但是很遗憾，这题用不了，因为有负数正数，窗口的滑动可能暂时让结果预期，但是往后遍历可能结果并不是最大的。比如[-3,2,0,-5]，最大的应该是整个数组和绝对值，但是滑动窗口可能结果是[-5]。

题解

/**
 * @Author: vividzcs
 * @Date: 2021/3/5 4:58 下午
 */
public class MaxAbsoluteSum {
    public static void main(String[] args) {
        int[] nums = {-3,-5,-3,-2,-6,3,10,-10,-8,-3,0,10,3,-5,8,7,-9,-9,5,-8};
        int result = maxAbsoluteSum(nums);
        System.out.println(result);
    }

    /**
     * 执行用时： 6 ms , 在所有 Java 提交中击败了 68.72% 的用户
     * 内存消耗： 47 MB , 在所有 Java 提交中击败了 81.56% 的用户
     */
    private static int maxAbsoluteSum(int[] nums) {
        if (nums.length < 1) {
            return 0;
        }
        int len = nums.length;
        int result = Integer.MIN_VALUE;
        int[] sums = new int[len + 1];
        sums[0] = 0;
        for (int i=1; i<len+1; i++) {
            sums[i] = sums[i-1] + nums[i-1];
        }
        int max = sums[0];
        int min = sums[0];
        for (int i=0; i<sums.length; i++) {
            if (sums[i] >= 0) {
                result = Math.max(result, Math.abs(sums[i] - min));
            } else {
                result = Math.max(result, Math.abs(sums[i] - max));
            }

            max = Math.max(max, sums[i]);
            min = Math.min(min, sums[i]);
        }
        return result;
    }
}