分析

• 本题的考点：动态规划。

• 本题是一个有限制的选择问题，类似的问题还有Leetcode 0198 打家劫舍，一般这种问题都可以使用动态规划解决。背包问题也属于此类问题，关于背包问题的总结可以参考：背包问题（背包九讲）。

• 因为所有的数据在1~10000之间，我们可以开一个数组cnt记录每个数据出现的次数。之后是动态规划的分析：

代码

• C++

const int N = 10010;
int cnt[N], f[N][2];

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {

        memset(cnt, 0, sizeof cnt);
        memset(f, 0, sizeof f);
        for (auto x : nums) cnt[x]++;
        int res = 0;
        for (int i = 1; i < N; i++) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + i * cnt[i];
            res = max(res, max(f[i][0], f[i][1]));
        }
        return res;
    }
};

• Java

class Solution {

    static final int N = 10010;
    int[] cnt = new int[N];
    int[][] f = new int[N][2];

    public int deleteAndEarn(int[] nums) {

        for (int x : nums) cnt[x]++;
        int res = 0;
        for (int i = 1; i < N; i++) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + i * cnt[i];
            res = Math.max(res, Math.max(f[i][0], f[i][1]));
        }
        return res;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为数据最大值。

• 空间复杂度：$O(n)$。