力扣 中等 740.删除并获得点数

题目介绍

题解

由题意可知，在选择了数组中元素 a 后，该元素以及所有等于 a−1 和 a+1 的元素都会从数组中删去，并获得 a 的点数。若还有多个值为 a的元素，由于所有等于 a−1 或 a+1 的元素已经被删除，我们可以直接删除 a并获得其点数。因此若选择了 a，所有等于 a 的元素也应一同被选择，才可以尽可能多地获得点数。

记元素 a 在数组中出现的次数为 Ca ，我们可以用一个数组 sum 记录数组 nums 中所有相同元素之和，即 sum[a]=x⋅Ca 。若选择了 a，则可以获取 sum[a] 点数，且无法再选择 a−1 和 a+1。例如示例二 ：其sum数组为[0,0,4,9,4] ，不可以选择数组相邻的两个数，这就转换成了198. 打家劫舍 链接 。在统计出 sum 数组后，可以直接用打家劫舍的代码求得最大点数。

代码如下：

class Solution {public int deleteAndEarn(int[] nums) {int maxVal = 0;for (int val : nums) {maxVal = Math.max(maxVal, val);}int[] sum = new int[maxVal + 1];for (int val : nums) {sum[val] += val;}return rob(sum);}public int rob(int[] nums) {int n = nums.length;if(n == 1){return nums[0];}if(n == 2){return Math.max(nums[0], nums[1]);}int[] dp = new int[n];dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);for(int i = 2; i < n; i++){dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);}return dp[n - 1];}
}