740. Delete and Earn

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

• new solution updated 2022.02.03

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int dp[10001] = {0,};
        for(auto& n : nums) dp[n] += n;
        int prev = 0, cur = 0;
        for(int i = 1; i < 10001; i++) {
            int sum = prev + dp[i];
            prev = cur;
            cur = max(cur, sum);
        }
        return max(prev,cur);
    }
};

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int dp[10001] = {0,};
        unordered_map<int, int> m;
        for(auto& n : nums) m[n]++;
        dp[1] = m[1];
        for(int i = 2; i < 10001; i++) {
            dp[i] = max(dp[i-1], dp[i-2] + i * m[i]);
        }
        return dp[10000];
    }
};

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        vector<int> sum(10001, 0);
        for(auto& n : nums) sum[n] += n;
        int get = 0, skip = 0;
        for(int i = 1; i <= 10000; i++) {
            int s = skip + sum[i];
            skip = max(get, skip);
            get = s;
        }
        return max(skip, get);
    }
};