摘要: 本文介绍最大子数组和的一类变种:和最大改为和的绝对值最大
【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings
在文章 最大子数组和的三种解法 中,我们详细拆解了最大子数组和这个问题,并且了解到这个问题有三种解法,都非常主流,并且各个方法都有它适用的变种问题。
前面我们已经研究了很多类型的变种问题,这里做一个小结,如下:
变种类型 | 文章 | 算法 |
---|---|---|
数组->矩阵 | 最大子矩阵和 | 转化为一维数组上的问题 |
数组->环形数组 | 环形数组上的最大子数组和 | 转化为一维数组上的问题 |
和有大小限制 | 带大小限制的最大子数组/子矩阵和 | 前缀和+单调队列,稍微修改 |
子数组长度有限制 | 带长度限制的最大子数组和 | 前缀和+单调队列,稍微修改 |
求和改为乘积 | 最大子数组乘积 | 动态规划,处理零和负数问题 |
数组可以增删改 | 增删改后的最大子数组和 | 动态规划+后处理 |
本文我们继续看一个变种,求最大的子数组和的绝对值。也就是基础问题是找到子数组,使得和最大,这里的问题是找到子数组,使得和的绝对值最大。
本题也给出了一种面对带绝对值的目标函数时的处理方法。
题目
给你一个整数数组 nums 。一个子数组 [nums[l], nums[l]+1, …, nums[r]-1, nums[r]] 的 和的绝对值 为 abs(nums[l] + nums[l]+1 + … + nums[r]-1 + nums[r]) 。
请你找出 nums 中 和的绝对值 最大的任意子数组(可能为空),并返回该 最大值 。
提示:
1 | 1 <= nums.length <= 1e5 |
示例 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 | 状态定义: |
代码 (C++)
1 | class Solution { |
算法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 | class Solution { |
算法3: 分治
对于左闭右开区间 [left, right)
,它的长度为 length = right - left
。
令 mid = (length + 1) / 2 + left
,可以得到两个左闭右开的子区间 [left, mid), [mid, right)
。
[left, right)
上和的绝对值最大的子串的位置有三种情况:
- 完全在左半区间
[left, mid)
:直接递归,需要 次 - 完全在右半区间
[mid, right)
:直接递归,需要 次 - 两个半区间各占一部分:在递归的回溯阶段做,这部分需要
三种情况的最大子串和的绝对值分别记为 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)
。
分治法的时间复杂度为 ,不如动态规划的 。
代码 (C++)
1 | class Solution { |