n উপাদানের একটি অ্যারে দেওয়া আছে। আমাদের অ্যারেটি থেকে সর্বোচ্চ সংখ্যক উপাদান নির্বাচন করতে হবে যাতে নির্বাচিত যেকোনো দুটি উপাদানের মধ্যে निरপেক্ষ পার্থক্য ১-এর চেয়ে বড় না হয়। উদাহরণস্বরূপ, অ্যারে [2, 2, 3, 4, 5] হলে উপাদানগুলো হবে ৩, কারণ সর্বোচ্চ গণনায় সিকোয়েন্স হবে 2, 2, 3।
০ এবং ১-এর निरপেক্ষ পার্থক্য মানে সংখ্যাগুলো x এবং x + 1 টাইপের হতে পারে। তাই আইডিয়া হলো অ্যারে উপাদানগুলোর ফ্রিকোয়েন্সি (আবৃত্তি) সংরক্ষণ করা। যেকোনো দুটি последователь (consecutive) উপাদানের ফ্রিকোয়েন্সি যোগফলের সর্বোচ্চ মানই সমাধান হবে।
উদাহরণ
#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
