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

5658. 任意子数组和的绝对值的最大值

给你一个整数数组 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

前缀和+峰值求解

求连续子数组的和的绝对值的最大值是求连续子数组的最小和与连续子数组的最大和的绝对值谁更大

思路：

• 找前缀和的峰值，最大值的$index$，这个index一定是子数组最大和的开始或者终止的端点的$index$
• 根据找到的这个端点，枚举另外一个端点，并记录子数组的最大和
• 找前缀和的峰值，最小的$index$，这个$index$一定是子数组最大和的开始或者终止的端点的$index$
• 根据找到的这个端点，枚举另外一个端点，并记录子数组的最小和
• 比较最大和与最小和的绝对值的大小，返回较大的那个

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n = nums.length;
        int pre[] = new int[n + 1];

        int min = pre[0];
        int minIndex = 0;
        int max = pre[0];
        int maxIndex = 0;
        // 计算前缀和，并记录最小值的index和最大值的index
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + nums[i - 1];
            if (pre[i] < min) {
                min = pre[i];
                minIndex = i;
            }
            if (pre[i] > max) {
                max = pre[i];
                maxIndex = i;
            }
        }

        min = Integer.MAX_VALUE;
        max = Integer.MIN_VALUE;
        // 枚举子数组的另外一个端点得到子数组最大的和
        for (int i = 0; i <= n; i++) {
            if (i == minIndex) continue;
            int sum = Math.abs(pre[minIndex] - pre[i]);
            max = Math.max(max, sum);
        }
        // 枚举子数组的另外一个端点得到子数组最小的和（中间求了绝对值，求最大即可）
        for(int i=0;i<=n;i++){
            if (i == maxIndex) continue;
            int sum = Math.abs(pre[maxIndex] - pre[i]);
            max = Math.max(max, sum);
        }
        return max;
    
    }
}
    

前缀和（优雅写法）

class Solution {
  public int maxAbsoluteSum(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
      nums[i] += nums[i-1];
    }
    Arrays.sort(nums);
    int max = nums[nums.length-1];
    int min = nums[0];
    int diff = Math.abs(max- min);
    return Math.max(Math.max(Math.abs(max),Math.abs(min)),diff);
  }
}

作者：hu-li-hu-wai
链接：https://leetcode-cn.com/problems/maximum-absolute-sum-of-any-subarray/solution/java-qian-zhui-he-by-hu-li-hu-wai-narg/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

贪心

任意区间和绝对值最大值 等价于 求前缀和任意两点差的最大值 即 最大值 与 最小值 的差

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n=nums.length;
        int sum=0;
        int max=0,min=0;

        for(int i=0;i<n;i++){
            sum += nums[i];
            // 求前缀和的最大值
            max = Math.max(sum,max);
            // 求前缀和的最小值
            min = Math.min(sum,min);
        }
        // 二者之差
        return max-min;
    }
}

赏

谢谢你请我吃糖果

微信