最大子数组和的绝对值

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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 <= 105
-1e4 <= nums[i] <= 104

示例 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_summax_summax_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(logN)$ 次
  2. 完全在右半区间 [mid, right):直接递归,需要 $O(logN)$ 次
  3. 两个半区间各占一部分:在递归的回溯阶段做,这部分需要 $O(N)$

三种情况的最大子串和的绝对值分别记为 left_result, right_result, mid_resultmax(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(NlogN)$,不如动态规划的 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