算法动态规划

目标带绝对值的处理：最大子数组和的绝对值

字数统计: 1.7k字   |   阅读时长: 7分
, , ,

摘要: 本文介绍最大子数组和的一类变种：和最大改为和的绝对值最大

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 最大子数组和的三种解法 中，我们详细拆解了最大子数组和这个问题，并且了解到这个问题有三种解法，都非常主流，并且各个方法都有它适用的变种问题。

前面我们已经研究了很多类型的变种问题，这里做一个小结，如下：

变种类型 文章 算法
数组->矩阵 最大子矩阵和 转化为一维数组上的问题
数组->环形数组 环形数组上的最大子数组和 转化为一维数组上的问题
和有大小限制 带大小限制的最大子数组/子矩阵和 前缀和+单调队列，稍微修改
子数组长度有限制 带长度限制的最大子数组和 前缀和+单调队列，稍微修改
求和改为乘积 最大子数组乘积 动态规划，处理零和负数问题
数组可以增删改 增删改后的最大子数组和 动态规划+后处理

本文我们继续看一个变种，求最大的子数组和的绝对值。也就是基础问题是找到子数组，使得和最大，这里的问题是找到子数组，使得和的绝对值最大。

本题也给出了一种面对带绝对值的目标函数时的处理方法。

题目

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

给你一个整数数组 nums 。一个子数组 [nums[l], nums[l]+1, …, nums[r]-1, nums[r]] 的 和的绝对值 为 abs(nums[l] + nums[l]+1 + … + nums[r]-1 + nums[r]) 。

请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。

提示：

1
2
1 <= nums.length <= 1e5
-1e4 <= nums[i] <= 1e4

示例 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[i] 结尾的最大子数组和 dp_max[i] 之外，再维护一个以 nums[i] 结尾的最小子数组和 dp_min[i]。

完整的算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
状态定义：
dp_max[i] := [0..i] 中，以 nums[i] 结尾的最大子数组和的绝对值
dp_min[i] := [0..i] 中，以 nums[i] 结尾的最小子数组和的绝对值

答案:
max(abs(dp_max[i]), abs(dp_min[i])

初始化：
dp_max[i] = nums[i]
dp_min[i] = nums[i]

状态转移:
dp_max[i] = max(dp_max[i - 1] + nums[i], nums[i])
dp_min[i] = min(dp_min[i - 1] + nums[i], nums[i])

代码 (C++)

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

算法2: 前缀和

在最大子数组和问题中，前缀和的做法是将 A[0..n-1] 的前缀和 sums[0..n] 求出之后，枚举每个前缀和的下标 1 <= j <= n，找到 0 < j - i <= N 时最大的 sums[j] - sums[i] 即为以 A[j - 1] 为结尾的最大子数组和，也就是要找最小的 sums[i]。

正因为加了绝对值，用前缀和还更简单了。因为 i 和 j 的位置关系以及 sums[i] 和 sums[j] 的大小关系决定了 sums[j] - sums[i] 的正负，由于加了一个绝对值，这个正负就不重要了，最终都会变成正的。

在不需要考虑 i, j 位置关系之后，直接找到最小的 sums[i] 和最大的 sums[j] 即可。于是就变成了在前缀和数组上分别取最小值 min_sum 和 max_sum，max_sum - min_sum 就是答案了。

代码 (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();
        vector<int> sums(n + 1);
        int max_sum = 0, min_sum = 0;
        for(int i = 1; i <= n; ++i)
        {
            sums[i] = nums[i - 1] + sums[i - 1];
            max_sum = max(max_sum, sums[i]);
            min_sum = min(min_sum, sums[i]);
        }
        return max_sum - min_sum;
    }
};

算法3: 分治

对于左闭右开区间 [left, right)，它的长度为 length = right - left。

令 mid = (length + 1) / 2 + left，可以得到两个左闭右开的子区间 [left, mid), [mid, right)。

[left, right) 上和的绝对值最大的子串的位置有三种情况：

  1. 完全在左半区间 [left, mid) ：直接递归，需要 $O(\log N)$ 次
  2. 完全在右半区间 [mid, right)：直接递归，需要 $O(\log N)$ 次
  3. 两个半区间各占一部分：在递归的回溯阶段做，这部分需要 $O(N)$

三种情况的最大子串和的绝对值分别记为 left_result, right_result, mid_result。max(left_result, right_result, mid_result) 就是 [left, right) 上的最大子串和的绝对值。递归终止条件为 length = 1。

我们要处理负数经过绝对值后变成正数可能会更大的情况，因此 mid_result 有两种可能得情况，一个是 abs(max_left_prod + max_right_prod)，另一个是 abs(min_left_prod + min_right_prod)。

分治法的时间复杂度为 $O(N\log N)$，不如动态规划的 $O(N)$。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int n = nums.size();
        return solve(nums, 0, n);
    }

    int solve(const vector<int>& nums, int left, int right)
    {
        // [left, right) 区间上的最大子数组的和的绝对值
        int length = right - left;
        if(length == 1)
            return abs(nums[left]);

        int mid = (length + 1) / 2 + left;

        int left_result = solve(nums, left, mid);
        int right_result = solve(nums, mid, right);

        // 横跨 [left, right) 的候选答案，一定包含 nums[mid - 1] 和 nums[mid]
        int right_sum = nums[mid];
        int max_right_sum = right_sum;
        int min_right_sum = right_sum;
        for(int i = mid + 1; i < right; ++i)
        {
            right_sum += nums[i];
            max_right_sum = max(max_right_sum, right_sum);
            min_right_sum = min(min_right_sum, right_sum);
        }
        int left_sum = nums[mid - 1];
        int max_left_sum = left_sum;
        int min_left_sum = left_sum;
        for(int i = mid - 2; i >= left; --i)
        {
            left_sum += nums[i];
            max_left_sum = max(max_left_sum, left_sum);
            min_left_sum = min(min_left_sum, left_sum);
        }
        int mid_result = max(abs(max_left_sum + max_right_sum), abs(min_left_sum + min_right_sum));

        return max(mid_result, max(left_result, right_result));
    }
};
Share