力扣---740. 删除并获得点数

给你一个整数数组 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/delete-and-earn
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

本题和小偷那题很相似https://www.cnblogs.com/allWu/p/16978811.html

假设有一个数是 n ，那么比 n - 1 小的数可获得的最大点数都对 n 没有影响，即 在数字 n 时 可获得的最大点数等于：1、比 n - 1 小的数可获得的最大点数之和加上数字 n 可获得的点数。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　  2、n - 1时可获得的最大点数。

两者取最大值即可。

当 n 从 0 逐渐增大到最大的数字时，也将逐渐接近可获得的最大点数。

代码如下：

 1 class Solution {
 2     public int deleteAndEarn(int[] nums) {
 3         int maxVal = 0;
 4         for (int val : nums) {
 5             maxVal = Math.max(maxVal, val);
 6         }
 7         // 定义一个长度为nums中最大数字 + 1 的数组，将 第 0 个位置不填，可以直接将数组下标作为对应的数字。
 8         int[] arr = new int[maxVal + 1];
 9         for (int a : nums) {
10             arr[a] += a;
11         }
12         
13         // 此处和小偷那道题几乎相同。
14         int max1 = arr[0];
15         int max2 = Math.max(arr[0], arr[1]);
16         for (int i = 2; i < arr.length; i ++) {
17             int tem = Math.max(max1 + arr[i], max2);
18             max1 = max2;
19             max2 = tem;
20         }
21         return max2;
22     }
23 }

运行结果如下：