ধরুন আমাদের কাছে পূর্ণসংখ্যার একটি অ্যারে সংখ্যা আছে, আমরা অ্যারেতে কিছু অপারেশন করতে পারি। এখানে প্রতিটি ক্রিয়াকলাপে, আমরা যেকোনো সংখ্যা[i] বাছাই করি এবং সংখ্যা[i] পয়েন্ট অর্জন করতে এটি মুছে ফেলি। আমাদের অবশ্যই nums[i] - 1 বা nums[i] + 1 এর সমান প্রতিটি উপাদান মুছে ফেলতে হবে। প্রাথমিকভাবে বিন্দু হল 0। এই ধরনের ক্রিয়াকলাপ প্রয়োগ করে আমাদের সর্বোচ্চ সংখ্যক পয়েন্ট অর্জন করতে হবে। সুতরাং যদি ইনপুটটি [3,4,2] এর মত হয়, তাহলে আউটপুট হবে 6। তাই এর কারণ, যদি আমরা 4 মুছে ফেলি, আমরা 4 পয়েন্ট পাব, ফলস্বরূপ 3টিও মুছে যাবে। তারপর 2 পয়েন্ট পেতে 2 মুছে দিন। মোট 6 পয়েন্ট অর্জিত হয়েছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=সংখ্যা অ্যারের আকার, মানচিত্র m সংজ্ঞায়িত করুন, ret :=0, সংখ্যাগুলিতে উপাদানগুলির ফ্রিকোয়েন্সি m এ সঞ্চয় করুন
-
cnt :=0
-
প্রতিটি জোড়ার জন্য এটি m
-
x :=এর চাবি
-
temp :=x * এর মান
-
it1 :=এর আগের দিকে পয়েন্ট করুন এবং it2 :=it1 এর আগের দিকে পয়েন্ট করুন
-
যদি cnt>=1 এবং x – it1> 1 এর কী, তাহলে temp :=m[it1 এর কী]
-
অন্যথায় যখন cnt>=2, তারপর temp :=temp + m[it2 এর কী]
-
a =m[it1 এর কী] যদি cnt>=1, অন্যথায় 0
-
m[এর কী] :=সর্বোচ্চ তাপমাত্রা এবং a
-
ret :=ret এবং temp এর সর্বোচ্চ
-
cnt 1 দ্বারা বাড়ান
-
-
রিটার্ন রিটার্ন
উদাহরণ(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
