ลบและรับใน C ++

สมมติว่าเรามีจำนวนเต็มอาร์เรย์ เราสามารถทำการดำเนินการบางอย่างกับอาร์เรย์ได้ ที่นี่ในแต่ละการดำเนินการ เราเลือก nums[i] และลบออกเพื่อรับ nums[i] จำนวนคะแนน เราต้องลบทุกองค์ประกอบที่เท่ากับ nums[i] - 1 หรือ nums[i] + 1 ในตอนแรกจุดคือ 0 เราต้องหาจำนวนคะแนนสูงสุดที่เราจะได้รับจากการดำเนินการดังกล่าว ดังนั้นหากอินพุตเป็น [3,4,2] ผลลัพธ์จะเป็น 6 นี่เป็นเพราะถ้าเราลบ 4 เราจะได้ 4 คะแนน ดังนั้น 3 จะถูกลบด้วย จากนั้นลบ 2 เพื่อรับ 2 คะแนน ได้รับคะแนนทั้งหมด 6 คะแนน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของอาร์เรย์ nums, กำหนด map m, ret :=0, เก็บความถี่ขององค์ประกอบเป็น nums เป็น m

• cnt :=0

• สำหรับแต่ละคู่ของ m

  • x :=คีย์ของมัน

  • อุณหภูมิ :=x * ค่าของมัน

  • it1 :=ชี้ไปที่ก่อนหน้าของมัน และ it2 :=ชี้ไปที่ก่อนหน้าของมัน1

  • ถ้า cnt>=1 และ x – คีย์ของมัน1> 1 แล้ว temp :=m[key of it1]

  • มิฉะนั้นเมื่อ cnt>=2 แล้ว temp :=temp + m[key of it2]

  • a =m[key of it1] if cnt>=1, มิฉะนั้น 0

  • m[key of it] :=max of temp และ a

  • ret :=สูงสุดของ ret และ temp

  • เพิ่มขึ้นอีก 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