C++で1回削除した場合の最大サブアレイ合計

これを解決するには、次の手順に従います-

• n：=配列のサイズ、および：=a [0]
• suff_with_del：=0、suff_with_out_del：=a [0]
• iからn–1の範囲のiの場合
  • 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
• return res

例（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