在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的最大值
增加cnt1
返回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