ลบและได้คะแนนใน C++

ให้อาร์เรย์ nums ทำการดำเนินการซ้ำ: เลือก nums[i] ลบออก ได้คะแนน nums[i] แต่ต้องลบ ทุกตัว ที่มีค่า nums[i]-1 และ nums[i]+1 ด้วย หาคะแนนสูงสุดที่ได้

ตัวอย่าง: [3,4,2] → 6 (ลบ 4 ได้ 4 คะแนน 3 ถูกลบอัตโนมัติ แล้วลบ 2 ได้ 2 คะแนน รวม 6)

ขั้นตอนการแก้ปัญหา (DP บนค่าที่ไม่ซ้ำ)

1. นับความถี่แต่ละค่าใน map m
2. เรียงค่าที่ไม่ซ้ำ (key ของ map) 從小到大
3. DP แบบ House Robber: สำหรับค่า x เรียงลำดับ:
   • คะแนนถ้าเลือก x = x * freq[x]
   • ถ้าค่าก่อนหน้า prev ติดกัน (x - prev == 1) → ไม่สามารถเลือกทั้งคู่ได้: dp[x] = max(dp[prev], x*freq[x] + dp[prev2])
   • ถ้าไม่ติดกัน → เลือกได้พร้อมกัน: dp[x] = dp[prev] + x*freq[x]
4. คืนค่าสูงสุด

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        map<int, int> freq;
        for (int x : nums) freq[x]++;
        int prev = -1, prev2 = -1;
        int take = 0, skip = 0;
        for (auto& [x, cnt] : freq) {
            int curTake = x * cnt;
            if (prev != -1 && x == prev + 1) {
                int newTake = skip + curTake;
                int newSkip = max(take, skip);
                take = newTake; skip = newSkip;
            } else {
                int best = max(take, skip);
                take = best + curTake;
                skip = best;
            }
            prev2 = prev; prev = x;
        }
        return max(take, skip);
    }
};

int main() {
    vector<int> v = {3,4,2};
    Solution ob;
    cout << ob.deleteAndEarn(v);
}

Input

[3,4,2]

Output

6