ऐसे तत्वों की अधिकतम संख्या ज्ञात कीजिए जिनका निरपेक्ष अंतर C++ में 1 से कम या बराबर हो

मान लीजिए कि हमारे पास n तत्वों की एक सरणी है। हमें सरणी से चयन करने के लिए तत्वों की अधिकतम संख्या का पता लगाना है, जैसे कि चुने हुए तत्वों में से किन्हीं दो के बीच पूर्ण अंतर 1 से कम या बराबर है। इसलिए यदि सरणी [2, 2, 3, 4, की तरह है, 5], तो तत्व 3 होगा, इसलिए अधिकतम गिनती वाला क्रम 2, 2, 3 है।

0 और 1 के पूर्ण अंतर का मतलब है कि संख्या x और x + 1 प्रकार की हो सकती है। तो विचार सरणी तत्वों की आवृत्तियों को संग्रहीत करना है। इसलिए यदि हम किन्हीं दो क्रमागत तत्वों का अधिकतम योग ज्ञात करें, तो यह समाधान होगा।

उदाहरण

#include <iostream>
#include <map>
using namespace std;
int maxElem(int arr[], int n) {
   map<int,int> occurrence;
   for(int i=0;i<n;++i){
      if(occurrence[arr[i]])
         occurrence[arr[i]] += 1;
      else
         occurrence[arr[i]] = 1;
   }
   int ans = 0, key;
   map<int,int>:: iterator it=occurrence.begin();
   while(it!=occurrence.end()) {
      key = it->first;
      ++it;
      if(occurrence[key+1]!=0)
      ans=max(ans,occurrence[key]+occurrence[key+1]);
   }
   return ans;
}
int main(){
   int arr[] = {2, 2, 3, 4, 5};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"Result is: " << maxElem(arr, n);
}

आउटपुट

Result is: 3