C++-এ ডিলিট অ্যান্ড আর্ন

একটি পূর্ণসংখ্যা অ্যারে nums দেওয়া আছে। আমরা কিছু অপারেশন করতে পারি। প্রতিটি অপারেশনে যেকোনো nums[i] বেছে নিয়ে ডিলিট করলে nums[i] পয়েন্ট मिलবে। তবে nums[i]-1 আর nums[i]+1 সমান সব উপাদানও ডিলিট করতে হবে। প্রাথমিক পয়েন্ট ০। এই অপারেশনগুলো প্রয়োগ করে সর্বোচ্চ কত পয়েন্ট অর্জন করা যায় তা বের করতে হবে। উদাহরণ: [3,4,2] হলে আউটপুট ৬। কারণ ৪ ডিলিট করলে ৪ পয়েন্ট, ফলে ৩-ও ডিলিট হয়। তারপর ২ ডিলিট করলে ২ পয়েন্ট। মোট ৬।

সমাধানের ধাপগুলো:

n := nums.size(), m ম্যাপ, ret := 0, nums-এর ফ্রিকোয়েন্সি m-এ স্টোর করুন।
cnt := 0
m-এর প্রতিটি পেয়ার it এর জন্য:
- x := it.key
- temp := x * it.value
- it1 := it-এর প্রিভিয়াস, it2 := it1-এর প্রিভিয়াস।
- যদি cnt >= 1 AND x - it1.key > 1, temp += m[it1.key]।
- অন্যथा যদি cnt >= 2, temp += m[it2.key]।
- a = (cnt >= 1 ? m[it1.key] : 0)
- m[it.key] := max(temp, a)
- ret := max(ret, temp)
- cnt++
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]