資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告