मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी संख्या है, हम सरणी पर कुछ संचालन कर सकते हैं। यहां प्रत्येक ऑपरेशन में, हम कोई भी अंक [i] चुनते हैं और अंक अर्जित करने के लिए इसे हटाते हैं [i] अंक अर्जित करते हैं। हमें अंक [i] - 1 या अंक [i] + 1 के बराबर प्रत्येक तत्व को हटाना होगा। प्रारंभ में बिंदु 0 है। हमें इस तरह के संचालन को लागू करके अधिकतम अंक प्राप्त करना होगा। तो अगर इनपुट [3,4,2] जैसा है, तो आउटपुट 6 होगा। तो ऐसा इसलिए है, क्योंकि अगर हम 4 को हटाते हैं, तो हमें 4 अंक मिलेंगे, फलस्वरूप 3 भी हटा दिए जाएंगे। फिर 2 अंक प्राप्त करने के लिए 2 हटाएं। कुल 6 अंक अर्जित किए गए।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
n :=nums array का आकार, मैप को परिभाषित करें m, ret :=0, तत्वों की आवृत्ति को nums में m में स्टोर करें
-
सीएनटी:=0
-
प्रत्येक जोड़ी के लिए यह मी
-
x :=इसकी कुंजी
-
अस्थायी :=x * इसका मान
-
it1 :=इसके पिछले को इंगित करें, और it2 :=it1 के पिछले को इंगित करें
-
यदि cnt>=1 और x - इसकी कुंजी1> 1 है, तो अस्थायी :=m[it1 की कुंजी]
-
अन्यथा जब cnt>=2, तब temp :=temp + m[key of it2]
-
a =m[key of it1] यदि cnt>=1, अन्यथा 0
-
एम [इसकी कुंजी]:=अधिकतम तापमान और एक
-
ret :=अधिकतम रिट और अस्थायी
-
1 द्वारा cnt बढ़ाएँ
-
-
वापसी रिट
उदाहरण(C++)
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int n = nums.size();
map <int, int> m;
int ret = 0;
for(int i = 0; i < nums.size(); i++){
m[nums[i]]++;
}
int cnt = 0;
map <int, int> :: iterator it = m.begin();
while(it != m.end()){
int x = it->first;
int temp = x * it->second;
map <int, int> :: iterator it1 = prev(it);
map <int, int> :: iterator it2 = prev(it1);
if(cnt >= 1 && x - it1->first > 1){
temp += m[it1->first];
}
else if(cnt >= 2){
temp += m[it2->first];
}
m[it->first] = max(temp, cnt >= 1 ? m[it1->first] : 0);
ret = max(ret, temp);
it++;
cnt++;
}
return ret;
}
};
main(){
vector<int> v = {3,4,2};
Solution ob;
cout << (ob.deleteAndEarn(v));
} इनपुट
[3,4,2]
आउटपुट
6