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

难度: 中等

来源: 每日一题 2023.08.08

---

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

class Solution {
    public int maxAbsoluteSum(int[] nums) {

    }
}

分析与题解

---

• 动态规划

  这个题目也是动态规划, 当我看到了求最大的和, 不管是普通的, 还是说其他奇奇怪怪的形式, 基本上是要考虑动态规划了.

  这个题目求绝对值的最大和, 那么就需要分两种情况讨论了. 一种是最小和(也就是和的最小值,可能是个负数, 一反转就变成整数了), 一种是最大和. 这两种情况我们都需要进行讨论.

  在下标 i 的情况下, 不考虑后面的元素, 只考虑前面的元素, 最大和/最小和子序列一共有两种情况.

  • nums[i]
  • num[i - 1]的最大和/最小和子序列 + nums[i]

  所以, 这样我们的状态转移方程就出现了, 并且我们不需要考虑 num[i - 1] 以前的值, 所以我们需要用常量进行保存即可.

  接下来我们看一下具体的解题步骤.

  首先我们定义两个状态转移方程常量 maxDp 和 minDp 用来表示当前下标i的子序列最大和/最小和.

  // 用dp表示当前下标i所有对应的最大值/最小值(不进行绝对值运算)
  int maxDp = 0, minDp = 0;
  

  然后, 我们进行遍历, 判断 nums[i] 和 num[i - 1]的最大和/最小和子序列 + nums[i] 大小情况.

  for (int i = 0; i < nums.length; i++) {
      maxDp = maxDp + nums[i] > nums[i] ? maxDp + nums[i] : nums[i];
      minDp = minDp + nums[i] < nums[i] ? minDp + nums[i] : nums[i];
      maxResult = Math.max(maxDp, maxResult);
      minResult = Math.min(minDp, minResult);
  }
  

  最后比较 maxResult 和 minResult 的绝对值即可.

  return Math.max(Math.abs(maxResult), Math.abs(minResult));
  
  

  整体的解题思路如下所示.

  class Solution {
      public int maxAbsoluteSum(int[] nums) {
          // 用dp表示当前下标i所有对应的最大值/最小值(不进行绝对值运算)
          int maxDp = 0, minDp = 0;
          int maxResult = 0, minResult = 0;
          for (int i = 0; i < nums.length; i++) {
              maxDp = maxDp + nums[i] > nums[i] ? maxDp + nums[i] : nums[i];
              minDp = minDp + nums[i] < nums[i] ? minDp + nums[i] : nums[i];
              maxResult = Math.max(maxDp, maxResult);
              minResult = Math.min(minDp, minResult);
          }
          return Math.max(Math.abs(maxResult), Math.abs(minResult));
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n), 时间复杂度与较短的链表长度相关.
  • 空间复杂度: O(1), 常量级别的空间复杂度.

  结果如下所示.