在C ++中删除和赚钱

假设我们有一个整数数组，可以对数组执行一些操作。在这里，在每个操作中，我们选择任何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：= 0

• 每对米

• x：=它的关键

• temp：= x *它的值

• it1：=指向它的前一个，而it2：=指向它的前一个

• 如果cnt> = 1并且x – it1的键> 1，则temp：= m [it1的键]

• 否则，当cnt> = 2时，则temp：= temp + m [it2的键]

• a = m [it1的键]如果cnt> = 1，否则为0

• m [它的键]：= 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