数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中允许删除一个元素的最大子数组和
假设我们有一个整数数组；我们必须找到一个非空子数组（连续元素）的最大和，最多允许删除一个元素。换句话说，我们可以选择一个子数组并从中可选地删除一个元素，这样至少还剩下一个元素，并且剩余元素的和最大。我们必须记住，删除一个元素后，子数组需要是非空的。所以如果输入像 [1,-2,0,3]，那么输出将是 4。如果我们删除 -2，它将返回最大和。
为了解决这个问题，我们将遵循以下步骤：
- n := 数组大小，ans := a[0]
- suff_with_del := 0, suff_with_out_del := a[0]
- 对于 i 从 0 到 n – 1 的范围
- suff_with_del := suff_with_del + a[i] 和 suff_with_out_del 的最大值
- suff_with_out_del := a[i] 和 suff_with_out_del + a[i] 的最大值
- ans := ans，suff_with_out_del 和 suff_with_del 的最大值
- 返回 ans
示例（C++）
让我们看看下面的实现来更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maximumSum(vector<int>& a) {
int n = a.size();
int ans = a[0];
int suffix_with_deletion = 0;
int suffix_with_not_deletion = a[0];
for(int i = 1;i<n;i++){
suffix_with_deletion = max(suffix_with_deletion + a[i], suffix_with_not_deletion);
suffix_with_not_deletion = max(a[i],suffix_with_not_deletion+a[i]);
ans = max({ans, suffix_with_not_deletion,suffix_with_deletion});
}
return ans;
}
};
main(){
vector<int> v = {1,-2,0,3};
Solution ob;
cout <<ob.maximumSum(v);
}输入
[1,-2,0,3]
输出
4
更新于：2020年4月30日
271 次浏览
广告