0740. Delete and Earn¶
题目信息¶
- 题号:
0740
- 难度:
Medium
- 主题:
数组、删除规则、最大得分
- 原题:
- 重点:
每次主动删除一个值可获得等于该值的分数,同时必须删除当时所有值为其相邻整数的元素;可操作任意多次并求最大总分
题目重述¶
给定正整数数组 nums。你可以执行任意多次以下操作:选择当前数组中的一个元素 nums[i],删除它并获得 nums[i] 分;随后必须同时删除当前所有值等于 nums[i] - 1 或 nums[i] + 1 的元素,这些被连带删除的元素不产生分数。
返回通过若干次操作能够获得的最大总分。相同数值可以出现多次;选择其中一个后,其他相同值不会被连带删除,之后仍可继续选择并得分。也允许在没有元素时停止操作。
数组长度在 [1, 2 * 10^4] 范围内,1 <= nums[i] <= 10^4。
自建示例¶
选择不相邻的数值组:
输入:nums = [1,1,2,4,4,5]
输出:10
解释:选择两个值 1 共得 2 分,并选择两个值 4 共得 8 分,总分为 10。选择 1 会删除值 2,选择 4 会删除值 5,但数值 1 与 4 互不影响。
多个相同值都可继续得分:
输入:nums = [7,7,8,9,9]
输出:32
解释:选择值 7 后会删除 8,但另一个 7 仍可选择,两个 7 共得 14 分;两个 9 也都可选择,共得 18 分,总分为 32。
数组只有一个元素:
输入:nums = [9]
输出:9
解释:唯一元素可以直接删除并获得 9 分,数组中不存在值 8 或 10 的元素需要连带删除,因此最大得分就是 9。