题目描述
给你一个整数数组,返回它的某个 非空 子数组(连续元素)在执行一次可选的删除操作后,所能得到的最大元素总和。
换句话说,你可以从原数组中选出一个子数组,并可以决定要不要从中删除一个元素。(删除后)子数组中至少应当有一个元素,然后该子数组(剩下)的元素总和是所有子数组之中最大的。
注意,删除一个元素后,子数组 不能为空。
样例
输入:arr = [1,-2,0,3]
输出:4
解释:我们可以选出 [1, -2, 0, 3],然后删掉 -2,这样得到 [1, 0, 3],和最大。
输入:arr = [1,-2,-2,3]
输出:3
解释:我们直接选出 [3],这就是最大和。
输入:arr = [-1,-1,-1,-1]
输出:-1
解释:最后得到的子数组不能为空,所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
我们应该直接选择 [-1],或者选择 [-1, -1] 再从中删去一个 -1。
限制
1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4
算法
(动态规划) $O(n)$
- 设 $f(i)$ 表示选中 $i$ 结尾的且没有删除过元素的最大子数组,$g(i)$ 表示以 $i$ 结尾的,但删除过元素的最大子数组。
- 初始时,$f(0) = a(0)$,$g(0) = -\infty$,其余元素待定。
- 转移时,对于 $f(i)$ 我们有两种选择,一种是用之前的结果和当前元素累加或者直接从当前元素重新开始。对于 $g(i)$,我们也有两种选择:不删除当前元素,即从 $g(i - 1) + arr(i)$ 转移;或者删除了当前元素,即从 $f(i - 1)$ 转移。
- 最终答案为 $\max(f(i), g(i))$。
时间复杂度
- 状态数为 $O(n)$,每次转移仅需 $O(1)$ 的时间,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要额外 $O(n)$ 的空间记录状态。
C++ 代码
class Solution {
public:
int maximumSum(vector<int>& arr) {
int n = arr.size();
vector<int> f(n), g(n);
int ans = arr[0];
f[0] = arr[0];
g[0] = -2000000000;
for (int i = 1; i < n; i++) {
f[i] = max(f[i - 1] + arr[i], arr[i]);
g[i] = max(g[i - 1] + arr[i], f[i - 1]);
ans = max(ans, max(f[i], g[i]));
}
return ans;
}
};
初始时, g[0] = 0 好理解一点 也可以过
一般建议非法状态设置为永远不会被取到的值会好一些,否则有时候会因为初始化造成了转移错误
666