सी++ में एक विलोपन के साथ अधिकतम सबअरे योग

मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी है; हमें एक गैर-रिक्त उपसरणी (सन्निहित तत्व) के लिए अधिकतम एक तत्व विलोपन के साथ अधिकतम योग खोजना होगा। दूसरे शब्दों में, हम कह सकते हैं कि हम एक उप-सरणी चुनना चाहते हैं और वैकल्पिक रूप से उसमें से एक तत्व को हटाना चाहते हैं ताकि कम से कम एक तत्व बचा रहे और शेष तत्वों का योग अधिकतम संभव हो। हमें यह ध्यान रखना होगा कि एक तत्व को हटाने के बाद उपसरणी को गैर-रिक्त होना चाहिए। इसलिए यदि इनपुट [1,-2,0,3] जैसा है, तो आउटपुट 4 होगा। इसलिए यदि हम -2 को हटाते हैं, तो यह अधिकतम योग लौटाएगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n :=सरणी का आकार, और :=a[0]
suff_with_del :=0, suff_with_out_del :=a[0]
i के लिए i से 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]
- उत्तर:=अधिकतम उत्तर, suff_with_out_del और suff_with _del
रिटर्न रेस

उदाहरण(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]