题目描述

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

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

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

示例 1：

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

共获得 6 个点数。

示例 2：

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

提示：

• 1 <= nums.length <= 2 * 104
• 1 <= nums[i] <= 104

思路

首先，nums 数组中包含了很多重复元素，因此我们需要对每个数字出现的次数进行统计。为了高效地进行统计，我们可以使用一个 countArray，其中 countArray[i] 表示数字 i 在 nums 中出现的次数。

接下来，我们可以选择删除某个数字。在删除该数字时，我们不仅要获得它本身的点数，还需要注意，删除该数字后，临近的元素（即 i-1 和 i+1）也会被删除。因此，如果我们选择了数字 i，我们必须避免同时选择 i-1 和 i+1，这使得我们只能选择不相邻的数字。

为了便于计算每个数字的得分，我们可以把每个数字的得分（即选择该数字能获得的点数）视为 i * countArray[i]，我们称其为该数字的“权重”。通过累加每个数字的权重，更新 countArray，我们得到了选择数字 i 后的点数。

举个例子，考虑 nums = [2, 2, 3, 3, 3, 4]，我们首先统计得到 countArray = [0, 0, 2, 3, 1]。然后，计算每个数字的权重，更新后的 countArray 变为 countArray = [0, 0, 4, 9, 4]。

此时，我们的目标就变成了：从更新后的 countArray 中选择哪些数字，以保证获得的点数最大。这其实是一个经典的动态规划问题，类似于“打家劫舍”问题，选择每个数字时需要避免选择与其相邻的数字，因此我们可以通过动态规划来求解这个问题。可以参考我之前发布的打家劫舍解决思路，很经典的动态规划问题。

经典动态规划问题-打家劫舍Java实现

代码实现

public int deleteAndEarn(int[] nums) {int N = 10001; // 由于 nums[i] 的范围是 [1, 10^4]，我们需要一个大小为 10001 的数组int[] countArray = new int[N];// 统计每个数字的出现次数for (int i = 0; i < nums.length; i++) {countArray[nums[i]]++;}// 将每个位置的值乘上它出现的次数，表示删除该数字获得的点数for (int i = 0; i < N; i++) {countArray[i] *= i;}// 如果数组只有一个元素，直接返回该元素的值if (nums.length == 1) {return nums[0];}// 初始化前两个数字的情况int prev1 = Math.max(countArray[0], countArray[1]); // prev1 表示删除到当前数字时获得的最大点数int prev2 = countArray[0]; // prev2 表示删除前一个数字时获得的最大点数// 遍历从第三个数字开始的情况int temp = 0;for (int i = 2; i < N; i++) {temp = Math.max(prev1, prev2 + countArray[i]); // 当前数字的最大点数 = max(不删除当前数字, 删除当前数字)prev2 = prev1; // 更新前一个状态prev1 = temp;  // 更新当前状态}// 返回最终的最大点数return temp;
}