740.删除并获得点数

练习次数 **

     https://leetcode.cn/problems/delete-and-earn/

                  740. 删除并获得点数
        中等 │ 961  │ 60.5% 的 215.7K │ 󰛨 提示

给你一个整数数组 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 * 10^4

* 1 <= nums[i] <= 10^4

func deleteAndEarn(nums []int) int {
 keyValue := map[int]int{}
 maxNum := 0

 for _, v := range nums {
  keyValue[v] += v
  if v > maxNum {
   maxNum = v
  }
 }

 dp := make([]int, maxNum+1)
 dp[0] = keyValue[0]
 dp[1] = max(keyValue[0], keyValue[1])

 for i := 2; i < maxNum+1; i++ {
  dp[i] = max(keyValue[i]+dp[i-2], dp[i-1])
 }

 return dp[maxNum]

}

func max(a, b int) int {
 if a < b {
  return b
 }
 return a
}