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[i]的元素之后，必须要删除nums[i] - 1和nums[i+1]的所有元素，所以我们需要对数组做一个排序，这样nums[i+1]和nums[i-1]就是两个相连在一起的数据了。
2. 他又需要获取操作操作的最大点数，所以我们需要对这些数做一个汇总。
3. 然后就可以遍历处理之后的数组了。举个例子，我们处理完的数据是a_map = {1:3,4:10, 2:12，3： 13}。后面用a_map来表示这个映射，，key表示原始数据，value表示汇总之后的数据。
4. 我们就可以获取到key之后，对他进行排序并遍历。（1，2，4】

开始判断要不删除当前元素

【1， 2， 3， 5】

当删除第一个元素可以获得数就是a_map[i]

删除第二个元素可以获得的数就是

判断第二个元素和第一个元素是否相邻的，如果是相邻的就从两个取一个最大值。如果不是就直接相加

依次排列。。。

由此我们的出的公式就是

不是相邻的
$$
s_i = a_map[nums_i] + s{i-1}
$$
相邻的
$$
s_i = max(a_map[nums_{i-2}] + nums_i, nums_{i - 1})
$$

代码

const deleteAndEarn = (nums: number[]): number => {     const map: { [key: number]: number } = nums.reduce((a: { [key: number]: number }, b: number): {         [key: number]: number     } => {         const value = a[b] || 0;         a[b] = value + 1         return a     }, {})     const keys = Object.keys(map)         .sort((a, b) => parseInt(a) - parseInt(b))         .map(item => parseInt(item));     const dp = new Array(nums.length).fill(0);     // 边界情况     if (nums.length === 0) return 0;     else if (keys.length === 1) return map[keys[0]] * keys[0]     // 给dp数组默认值     dp[0] = keys[0] * map[keys[0]]     // 开始写遍历     console.log(keys)     for (let i = 1; i < keys.length; i++) {         // 判断是不是属于i-1或者i+1的情况         if (keys[i] - 1 !== keys[i - 1]) {             dp[i] = keys[i] * map[keys[i]] + dp[i - 1];         } else {             // 这里是属于i-1或者i+1的情况             // 注意，需要注意一下当i是1时候我们要进行i-2，会有问题，所以我门这里也要单独判断一下。             let last_value: number             if (i === 1) {                 last_value = 0;             } else {                 last_value = dp[i - 2];             }             dp[i] = Math.max(last_value + keys[i] * map[keys[i]], dp[i - 1]);         }      }     return dp[keys.length - 1]; } 

结语
如果对您有帮助的话，您可以搜搜一下正在努力的迪迦关注一下此