delete-and-earn

class Solution {
public:
    map<int, int> dp , cnt;
    int next(int x){
        auto it = cnt.upper_bound(x);
        if(it==cnt.end()){
            return -1;
        }
        return it->first;
    }

    int f(int x){
        if(x==-1){
            return 0;
        }

        if(dp.find(x)!=dp.end()){
            return dp[x];
        }

        return dp[x] = max(x*cnt[x] + f(next(x+1)), f(next(x)));
    }

    int deleteAndEarn(vector<int>& nums) {
        int n = nums.size();
        dp.clear();
        cnt.clear();
        sort(nums.begin(), nums.end());
        int min_e = 1e9;
        // if I am picking a a[i], I should take all of the a[i]'s
        // f(x) = max(x*cnt[x] + f(next(x+1)), f(next(x)))
        // next(x) = next element > x in the map key

        for(auto x:nums){
            cnt[x]++;
            min_e = min(min_e, x);
        }

        return f(min_e);
    }
};