求最大连续子序列和的绝对值最大。
那么答案一定为最大子序列和或者最下子序列和。
DP方法
设 $f[i]$ 表示,以 $i$ 结尾的最大子序列和。
根据子序列长度可以划分为长度为 $1$ 或长度大于 $1$ 。
所以 $f[i] = max(f[i - 1] + a[i], a[i])$ 。
由于子序列可以为空,所以需要加上 $f[i] = max(f[i], 0)$ 。
class Solution {
public:
int maxAbsoluteSum(vector<int>& nums) {
int n = nums.size();
int mx = 0, mn = 0;
for (int i = 0, minv = 0, maxv = 0; i < n; i ++ ) {
maxv = max(nums[i], maxv + nums[i]);
minv = min(nums[i], minv + nums[i]);
mx = max(mx, maxv);
mn = min(mn, minv);
}
return max(abs(mn), mx);
}
};
前缀和方法
设 $maxv$ 表示前缀的最大值,$minv$ 表示前缀最小值。
那么答案为 $maxv - minv$ 。
分别考虑最大值端点在最小值哪边即可。
class Solution {
public:
int maxAbsoluteSum(vector<int>& nums) {
int s = 0, minv = 0, maxv = 0;
for (int x : nums) {
s += x;
maxv = max(maxv, s);
minv = min(minv, s);
}
return maxv - minv;
}
};