Delete and Earn.cpp

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        if (nums.empty())return 0;
        map<int, int> cnts;
        for (const auto& num : nums)++cnts[num];
        vector<vector<int>> dp(cnts.size(), vector<int>(2, INT_MAX));
        auto iter = cnts.begin();
        dp[0][0] = 0;
        dp[0][1] = cnts[iter->first] * iter->first;
        int n = cnts.size(), prev = iter->first;
        ++iter;
        for(int i = 1; i < n; ++i, ++iter)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = iter->first - prev == 1 ? cnts[iter->first] * iter->first + dp[i - 1][0] : cnts[iter->first] * iter->first + max(dp[i - 1][0], dp[i - 1][1]);
            prev = iter->first;
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};