题目描述
给你一个整数数组 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
算法
(前缀和,贪心) $O(n)$
- 由于绝对值最大意味着正的最大值或者负的最小值。所以,分别用
mi
和ma
记录遍历过程中遇到的前缀和的最大值和最小值,初始时都为 0。 - 对于当前前缀和
s
,用abs(s - mi)
和abs(s - ma)
来更新答案,然后用s
来更新mi
和ma
。
时间复杂度
- 遍历数组一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int maxAbsoluteSum(vector<int>& nums) {
const int n = nums.size();
int mi = 0, ma = 0, s = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
s += nums[i];
ans = max(ans, max(abs(s - mi), abs(s - ma)));
mi = min(mi, s);
ma = max(ma, s);
}
return ans;
}
};