题目地址
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;
}
}
