मान लीजिए हमारे पास इंटीजर्स का एक ऐरे है; हमें अधिकतम एक एलिमेंट डिलीशन के साथ नॉन-खाली सबएरे (सन्निहित एलिमेंट्स) के लिए अधिकतम सम ढूंढना है। दूसरे शब्दों में, हम कह सकते हैं कि हम एक सबएरे चुनना चाहते हैं और वैकल्पिक रूप से उससे एक एलिमेंट डिलीट करना चाहते हैं ताकि कम से कम एक एलिमेंट बचा रहे और शेष एलिमेंट्स का सम अधिकतम संभव हो। हमें ध्यान रखना होगा कि एक एलिमेंट डिलीट करने के बाद सबएरे नॉन-खाली होना चाहिए। यदि इनपुट [1,-2,0,3] है, तो आउटपुट 4 होगा। इसलिए यदि हम -2 को डिलीट करते हैं, तो यह अधिकतम सम लौटाएगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- n := ऐरे का आकार, ans := a[0]
- suff_with_del := 0, suff_with_out_del := a[0]
- i के लिए 1 से 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
