题目描述
给你一个整数数组 nums
。一个子数组 [nums_l, nums_{l + 1}, ..., nums{r - 1}, nums_r]
的 和的绝对值 为 abs(nums_l + nums_{l + 1} + ... + nums_{r - 1} + nums_r)
。
请你找出 nums
中 和的绝对值 最大的任意子数组(可能为空),并返回该 最大值 。
abs(x)
定义如下:
- 如果
x
是负整数,那么abs(x) = -x
。 - 如果
x
是非负整数,那么abs(x) = x
。
样例
输入:nums = [1,-3,2,3,-4]
输出:5
解释:子数组 [2,3] 和的绝对值最大,为 abs(2+3) = abs(5) = 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
算法1
最大连续和
- 通过LeetCode 53. 最大子序和 这题题解的思路,使用动态规划的方式分别求出最大连续和
maxv
以及 最小连续和minv
,再对maxv
和-minv
进行比较即可
时间复杂度 $O(n)$
C++ 代码
class Solution {
public:
int maxAbsoluteSum(vector<int>& nums) {
int n = nums.size();
vector<int> f(n + 1), g(n + 1);
int minv = 0, maxv = 0;
for(int i = 1;i <= n;i ++)
{
f[i] = max(nums[i - 1], f[i - 1] + nums[i - 1]);
g[i] = min(nums[i - 1], g[i - 1] + nums[i - 1]);
maxv = max(maxv, f[i]);
minv = min(minv, g[i]);
}
if(maxv >= -minv) return maxv;
return -minv;
}
};
算法2
前缀和
- 1、计算出数组的前缀和
- 2、使用
minv
和maxv
分别记录前面枚举过的 最小前缀和 以及 最大前缀和 - 3、当枚举到
i
位置时,通过minv
和maxv
计算出到i
为止的最大连续和s[i] - minv
和 最小连续和s[i] - maxv
,通过这两个值更新res
时间复杂度 $O(n)$
C++ 代码
class Solution {
public:
int maxAbsoluteSum(vector<int>& nums) {
int n = nums.size();
vector<int> s(n + 1);
for(int i = 1;i <= n;i ++) s[i] = s[i - 1] + nums[i - 1];
int res = 0;
int minv = 0, maxv = 0;
for(int i = 1;i <= n;i ++)
{
res = max(res, abs(s[i] - minv));
res = max(res, abs(s[i] - maxv));
minv = min(minv, s[i]);
maxv = max(maxv, s[i]);
}
return res;
}
};