力扣 1749 题：任意子数组和的绝对值的最大值（DP 与前缀和）

方法 1：前缀和

思路

这道题要找 nums 数组中和的绝对值最大的任意子数组，子数组的问题，我们可以使用前缀和的思想来做，假设前缀和数组是 s。

• 那么子区间的前缀和绝对值可以这样表示：|s[j] - s[i]|
• 我们不难发现，s[j] 跟 s[i] 相差越大，上式也就越大。
• 因此我们只需要找 s 数组中的最大前缀和跟最小前缀和，然后求差即可：max(s) - min(s)
• 因为存在负数的情况，貌似不好理解，所以可以分两种情况理解，在 s 数组中：
  • 如果最大前缀和出现在最小前缀和的右边，那么上式算的是最大子数组和。
  • 如果最大前缀和出现在最小前缀和的左边，那么上式算的是最小子数组和的绝对值。

还有一个更好理解的方式，就是想象是在爬山，本质上就是在计算最大的高度差。

拿案例 1 举例：

输入：nums = [1,-3,2,3,-4] 输出：5 

代码如下

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n = nums.length;
        int s = 0;
        int max = 0;
        int min = 0;
        for (int i = 0; i < n; i++) {
            s += nums[i];
            // 效率更高的写法
            if (max < s) {
                max = s;
            } else if (s < min) {
                min = s;
            }
        }
        return max - min;
    }
}

方法 2：动态规划

这道题也可以使用动态规划的写法，这道题属于线性的动态规划。

思路

1. 考虑以 nums[i] 结尾的最大子数组和（以 nums[i] 结尾的最小子数组逻辑是一样的）
   • 如果子数组只有自己一个数，那么最大子数组和就是 nums[i]
   • 如果跟前面拼接起来，那么就变成了求更小的子问题：求以 nums[i-1] 结尾的最大子数组和
2. 定义状态:
   • 设 f[i] 为以 nums[i] 结尾的最大子数组和。
   • 设 g[i] 为以 nums[i] 结尾的最小子数组和。
3. 状态转移方程：
   • 最大值： f[i] = max(f[i-1] + nums[i], nums[i])
     • 意为：要么接在前面的最大和后面，要么自己重新开始。
   • 最小值： g[i] = min(g[i-1] + nums[i], nums[i])
     • 意为：要么接在前面的最小和后面，要么自己重新开始。
4. 最终答案：
   • maxSum = max(maxSum, f[i])
   • minSum = min(minSum, g[i])

最后返回：max(maxSum, -minSum)

代码

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n = nums.length;
        // 表示以 nums[i] 结尾的最大子数组和
        int[] f = new int[n];
        // 表示以 nums[i] 结尾的最小子数组和
        int[] g = new int[n];
        // 初始化
        f[0] = nums[0];
        g[0] = nums[0];
        int ans = Math.abs(nums[0]);
        for (int i = 1; i < n; i++) {
            // 状态转移：要么接上前面的，要么从当前推倒重来
            f[i] = Math.max(nums[i], f[i-1] + nums[i]);
            g[i] = Math.min(nums[i], g[i-1] + nums[i]);
            // 当前最大和、当前最小和的绝对值、以及之前的最大绝对值
            ans = Math.max(ans, Math.max(f[i], -g[i]));
        }
        return ans;
    }
}

这个方法好理解一下，我们也可以更优雅的写法：使用空间优化的方法，如下：

空间优化的写法

因为求 f[i] 的公式是：f[i] = max(nums[i], f[i-1] + nums[i])

f[i] 只根据前一次的数据 f[i-1]，至于更早的数据，对于 i 来说都不需要，所以，我们可以使用滚动变量的方式进行空间优化：

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        // 1. 先显式初始化第一个元素
        int fMax = nums[0];
        int fMin = nums[0];
        int ans = Math.abs(nums[0]);
        // 2. 从 i = 1 开始循环
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            fMax = Math.max(x, fMax + x);
            fMin = Math.min(x, fMin + x);
            ans = Math.max(ans, Math.max(fMax, -fMin));
        }
        return ans;
    }
}

或者：

• 不使用空间优化时，状态转移方程是：f[i] = max(nums[i], f[i-1] + nums[i])
• 这个方程可以提取出 nums[i]，写成：f[i] = max(0, f[i-1]) + nums[i]

所以当你使用空间优化，把数组 f[i] 变成变量 fMax 时，代码可以写成：

fMax = Math.max(fMax, 0) + x;

且在第一轮循环结束后，fMax 和 fMin 都会被'强制校准'为数组的第一个元素

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int ans = 0, fMax = 0, fMin = 0;
        for (int x : nums) {
            fMax = Math.max(fMax, 0) + x;
            fMin = Math.min(fMin, 0) + x;
            ans = Math.max(ans, Math.max(fMax, -fMin));
        }
        return ans;
    }
}