740. Delete and Earn

https://leetcode.com/problems/delete-and-earn/

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int max_val = *max_element(nums.begin(), nums.end());
        vector<int> values(max_val+1, 0);
        
        for(int num: nums) {
            values[num] += num;
        }
        
        int dp[max_val+ 1];
        dp[0] = values[0];
        dp[1] = max(values[0], values[1]);
        for(int i = 2; i < max_val + 1; i++) {
            dp[i] = max(dp[i-2] + values[i], dp[i-1]);
        }
        return max(dp[max_val], dp[max_val-1]);
    }
};

best

class Solution {
public:
    int getDE(int mx,vector<int>&freq,vector<int>&dp)
    {
        if(mx==0)
            return 0;
        if(mx==-1)
            return 0;
        if(dp[mx]!=-1)
            return dp[mx];
        int pick=mx*freq[mx]+getDE(mx-2,freq,dp);
        int notpick=getDE(mx-1,freq,dp);
        return dp[mx]=max(pick,notpick);
    }
    int deleteAndEarn(vector<int>& nums) {
        int n=nums.size();
        int mx=*max_element(nums.begin(),nums.end());
        vector<int>dp(mx+1,0);
        vector<int>freq(mx+1,0);
        for(int i=0;i<n;i++)
        {
            freq[nums[i]]++;
        }
        dp[0]=0;
        dp[1]=1*freq[1];
        for(int i=2;i<=mx;i++)
        {
            dp[i]=max(dp[i-1],freq[i]*i+dp[i-2]);
        }
        return dp[mx];
    }
};