LeetCode 1186. 删除一次得到子数组最大和(前后缀分解 | 状态机DP)
原题链接
中等
作者:
autumn_0
,
2024-07-21 00:53:56
,
所有人可见
,
阅读 6
前后缀分解
class Solution {
public:
int maximumSum(vector<int>& a) {
int n = a.size();
int f[n], g[n];
f[0] = a[0];
int res = a[0];
for(int i = 1; i < n; i ++ )
{
f[i] = max(f[i - 1], 0) + a[i];
res = max(res, f[i]);
}
g[n - 1] = a[n - 1];
for(int i = n - 2; i >= 0; i -- )
g[i] = max(g[i + 1], 0) + a[i];
for(int i = 1; i < n - 1; i ++ )
res = max(res, f[i - 1] + g[i + 1]);
return res;
}
};
状态机DP
class Solution {
public:
int maximumSum(vector<int>& a) {
int n = a.size();
int f[n], g[n];
int INF = 2e9;
f[0] = a[0], g[0] = -INF;
int res = a[0];
for(int i = 1; i < n; i ++ )
{
f[i] = max(f[i - 1], 0) + a[i];
g[i] = g[i - 1] + a[i];
if(i >= 2) g[i] = max(g[i], f[i - 2] + a[i]);
res = max({res, f[i], g[i]});
}
return res;
}
};