3186. Maximum Total Damage With Spell Casting

A magician has various spells.

You are given an array power, where each element represents the damage of a spell. Multiple spells can have the same damage value.

It is a known fact that if a magician decides to cast a spell with a damage of power[i], they cannot cast any spell with a damage of power[i] - 2, power[i] - 1, power[i] + 1, or power[i] + 2.

Each spell can be cast only once.

Return the maximum possible total damage that a magician can cast.

class Solution {
public:
    long long maximumTotalDamage(vector<int>& A) {
        sort(rbegin(A), rend(A));
        map<long long, long long> dp;
        long long res = 0, best = 0;
        while(A.size()) {
            long long now = 0, x = A.back();
            while(A.size() and A.back() == x) {
                now += x;
                A.pop_back();
            }
            while(dp.size() and begin(dp)->first < x - 2) {
                best = max(best, begin(dp)->second);
                dp.erase(begin(dp));
            }
            dp[x] = max(dp[x], best + now);
            res = max(res, dp[x]);
        }
        return res;
    }
};