LeetCode 1186. 删除一次得到子数组最大和 (最大子串和的变种)

1186. 删除一次得到子数组最大和 只要比最大子串和的多一个状态划分即可。

$f[i][0]$表示以$i$位结束的子串如果一次不删的话，获得的最大和。$f[i][1]$表示 class Solution { public: int f[100100][2], inf = 0xcfcfcfcf, ans; int maximumSum(vector<int>& a) { f[0][0] = a[0]; f[0][1] = inf; // 不允许全为空 ans = f[0][0]; for(int i=1;i<a.size();i++){ f[i][0] = max(f[i-1][0]+a[i],a[i]); // 与最大子串和的转移一样 f[i][1] = max(f[i-1][1]+a[i],f[i-1][0]); ans = max(ans,max(f[i][0],f[i][1])); } return ans; } };