C++で削除して獲得する

整数の配列numsがあるとすると、配列に対していくつかの操作を実行できます。ここでは、各操作で、任意の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

• ペアごとにm

  • x：=その鍵

  • temp：=x*その値

  • it1：=前を指す、it2：=前を指す1

  • cnt> =1かつx–it1のキー>1の場合、temp：=m[it1のキー]

  • それ以外の場合、cnt> =2の場合、temp：=temp + m [key of it2]

  • a =m [key of it1] cnt> =1の場合、それ以外の場合は0

  • m [キー]：=温度の最大値と

  • 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