1. 题目描述

给定一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于nums[i] - 1 或 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：

1
2
3
4
5

输入: nums = [3, 4, 2]
输出: 6
解释: 
删除 4 来获得 4 个点数，因此 3 也被删除。
之后，删除 2 来获得 2 个点数。总共获得 6 个点数。

示例 2：

1
2
3
4
5
6

输入: nums = [2, 2, 3, 3, 3, 4]
输出: 9
解释: 
删除 3 来获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。

提示：

• nums的长度最大为20000。
• 每个整数nums[i]的大小都在[1, 10000]范围内。

2. 思路

先用示例2来说明一下题目的意思，假设我们现在有nums = [2, 2, 3, 3, 3, 4]，我们开始随便选一个数字，如果选了2，那么数组中所有的1和3都要删掉，并此次选数的得分为2；删除完毕后，我们继续选数字，然后按照类似的方式删除数，并加上选数的得分…一直这么进行下去，直到无法再选任何一个数字，此时的总得分为我们的得分，现在就希望求得最高得分。

经过这么一解读，这个题目和>>LeetCode-198-打家劫舍<<很相似，可以参考>>我的题解-LeetCode-198-打家劫舍<<，在这里，相邻的房子就是相邻的整数了，所以我们需要对nums数组中各个整数的数量统计一遍。注意，题目中有说这些整数的范围为[1, 10000]，所以统计数组需要的空间复杂度为O(1)。

怎么类比打家劫舍的思路呢(>>参考<<)？同样用示例2作为例子：

• 首先，我们统计各个正整数出现的次数，得到cnts=[0,0,2,3,1],其中cnts[i]表示正整数i的出现次数；

• 然后，同样假设前面的决策已经是最优的，用数组dp[i]记录正整数1~i的选择完毕后对应的最大得分，现在我们只需判断最后一个，也就是这里的4：

  • 如果我们在选数的时候选了4，那么数字3肯定不能在之前被选（不然4早就被删除了），所以此时最优得分为dp[4-2]+cnts[4]*4;
  • 如果我们选数的时候不选4，那么肯定是选了数字3，故此时最优得分为dp[3]。

• so，转移方程自然就出来了：

  $$\begin{aligned} dp[i]&=max\{dp[i-1],dp[i-2]+dp[i]*nums[i]\}, for \space i \space =2,3,4,...,N \\ dp[1]&=cnts[1]*1\\ dp[2]&=max\{dp[1], \space nums[2]*2\}\\ \end{aligned}$$

动态转移方程的初始条件需要考虑选1和选2两种情况。

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
       public int deleteAndEarn(int[] nums) {
        if (nums.length < 1)
            return 0;
        if (nums.length == 1)
            return nums[0];

        // get max integer in nums.
        int max = nums[0];
        for (int i = 0; i < nums.length; ++i) {
            max = Math.max(max, nums[i]);
        }

        // count the nums
        int[] cnts = new int[max + 1];
        for (int i = 0; i < nums.length; i++)
            cnts[nums[i]]++;

        int[] dp = new int[max + 1];
        // find the minimum number that occurs no less than once.
        dp[1] = cnts[1] * 1;
        dp[2] = Math.max(dp[1], cnts[2] * 2);
        for (int i = 2; i <= max; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * cnts[i]);
        }
        return dp[max];

    }

}

4. 相似题

• >>LeetCode-198-打家劫舍<<

• ← Previous Post
• Next Post →