मान लीजिए हमारे पास पूर्णांकों की एक सरणी nums है, हम सरणी पर कुछ ऑपरेशन कर सकते हैं। यहां प्रत्येक ऑपरेशन में, हम कोई nums[i] चुनते हैं और उसे हटाकर nums[i] अंक अर्जित करते हैं। हमें nums[i] - 1 या nums[i] + 1 के बराबर हर तत्व को हटाना होगा। प्रारंभ में अंक 0 है। हमें ऐसे ऑपरेशन लागू करके अर्जित किए जा सकने वाले अधिकतम अंक ढूंढने हैं।
उदाहरण के लिए, यदि इनपुट [3,4,2] जैसा है, तो आउटपुट 6 होगा। ऐसा इसलिए है क्योंकि, यदि हम 4 हटाते हैं, तो हमें 4 अंक मिलेंगे, परिणामस्वरूप 3 भी हट जाएगा। फिर 2 को हटाकर 2 अंक प्राप्त करें। कुल 6 अंक अर्जित किए गए।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := nums सरणी का आकार, मैपmपरिभाषित करें,ret := 0,numsमें तत्वों की आवृत्ति कोmमें संग्रहीत करेंcnt := 0mके प्रत्येक जोड़ीitके लिएx := it की कुंजीtemp := x * it का मानit1 := it के पिछले को इंगित करें, औरit2 := it1 के पिछले को इंगित करें- यदि
cnt >= 1 और x - it1 की कुंजी > 1, तोtemp := m[it1 की कुंजी] - अन्यथा जब
cnt >= 2, तोtemp := temp + m[it2 की कुंजी] a = m[it1 की कुंजी] यदि cnt >= 1, अन्यथा 0m[it की कुंजी] := temp और a का अधिकतमret := ret और temp का अधिकतमcntको 1 से बढ़ाएं
retलौटाएं
उदाहरण (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