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

题目描述

这是 LeetCode 上的 1749. 任意子数组和的绝对值的最大值 ，难度为 中等。

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

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

输出：5

解释：子数组 [2,3] 和的绝对值最大，为 abs(2+3) = abs(5) = 5 。

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

输出：8

解释：子数组 [-5,1,-4] 和的绝对值最大，为 abs(-5+1-4) = abs(-8) = 8 。

提示：

  • $1 <= nums.length <= 10^5$
  • $-10^4 <= nums[i] <= 10^4$

前缀和

题目要我们求连续一段的子数组的和，很自然就能想到前缀和。

当我们有了前缀和数组 sum 之后，需要求任意一段子数组 [i,j] 的和可以直接通过 sum[j] - sum[i - 1] 得出。

要使得 abs(sum[j] - sum[i - 1]) 最大，其实有这么几种情况：

  • 找到前缀和数组中的最大值减去最小值，得到一个最大正数（前提是最大值出现在最小值的后面，并且最小值是个负数，否则应该直接取最大值作为答案）
  • 找到前缀和的最小值减去最大值，得到一个最小负数（前提是最小值出现在最大值的后面，而且最大值是一个正数，否则直接取最小值作为答案）。

也就是说最终答案只与前缀和数组中的最大值和最小值相关，而且最大值可能会出现在最小值前面或者后面。

因此我们可以边循环边做更新答案。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n = nums.length, ans = 0;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        for (int i = 1, min = 0, max = 0; i <= n; i++) {
            ans = Math.max(ans, Math.abs(sum[i] - min));
            ans = Math.max(ans, Math.abs(sum[i] - max));
            max = Math.max(max, sum[i]);
            min = Math.min(min, sum[i]);
        }
        return ans;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        vector<int> sumv(n + 1, 0);
        for (int i = 1; i <= n; i++) sumv[i] = sumv[i - 1] + nums[i - 1];
        for (int i = 1, minv = 0, maxv = 0; i <= n; i++) {
            ans = max(ans, abs(sumv[i] - minv));
            ans = max(ans, abs(sumv[i] - maxv));
            maxv = max(maxv, sumv[i]);
            minv = min(minv, sumv[i]);
        }
        return ans;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxAbsoluteSum(self, nums: List[int]) -> int:
        n, ans = len(nums), 0
        sumv = [0] * (n + 1)
        for i in range(1, n + 1):
            sumv[i] = sumv[i - 1] + nums[i - 1]
        minv, maxv = 0, 0
        for i in range(1, n + 1):
            ans = max(ans, abs(sumv[i] - minv))
            ans = max(ans, abs(sumv[i] - maxv))
            maxv = max(maxv, sumv[i])
            minv = min(minv, sumv[i])
        return ans

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
function maxAbsoluteSum(nums: number[]): number {
    let n = nums.length, ans = 0;
    const sum = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
    for (let i = 1, min = 0, max = 0; i <= n; i++) {
        ans = Math.max(ans, Math.abs(sum[i] - min));
        ans = Math.max(ans, Math.abs(sum[i] - max));
        max = Math.max(max, sum[i]);
        min = Math.min(min, sum[i]);
    }
    return ans;
};

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1749 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。