- 问题描述
- 给你一个整数数组
nums，你可以对它进行一些操作。每次操作中，你可以选择数组中的一个元素并删除它，同时获得该元素的点数。 - 删除一个元素后，该元素的左右相邻元素会变成相邻元素。
- 你需要返回你能获得的最大点数。
- 示例分析
- 例如，给定数组
nums = [2, 2, 3, 3, 3, 4]。 - 如果选择删除数字 2，会获得 2*2 = 4 点（有两个 2）。然后数组变为
[3, 3, 3, 4]。 - 如果选择删除数字 3，会获得 3*3 = 9 点（有三个 3）。然后数组变为
[4]。 - 如果选择删除数字 4，会获得 4 点。
- 最终，通过合理选择删除的数字，可以获得的最大点数为 4 + 9 + 4 = 17。
- 解题思路
- 动态规划：
- 首先，统计数组中每个数字的出现次数。
- 然后，考虑选择删除某个数字时，其相邻数字不能被选择删除。这就意味着我们需要在相邻数字的点数中做出权衡。
- 设
dp[i]表示以数字i结尾时能获得的最大点数。如果数字i在数组中不存在，那么dp[i] = 0。 - 对于数字
i，如果它在数组中的出现次数为count，那么有两种情况：
- 选择删除数字
i，此时获得的点数为i * count，并且不能选择删除数字i - 1和i + 1，所以dp[i] = i * count + dp[i - 2]（因为不能选择i - 1，所以考虑dp[i - 2]）。 - 不选择删除数字
i，那么dp[i] = dp[i - 1]。
- 最终的结果为
dp数组中的最大值。
- 代码实现
def deleteAndEarn(nums): max_num = max(nums) freq = [0] * (max_num + 1) for num in nums: freq[num] += 1 dp = [0] * (max_num + 1) dp[1] = freq[1] for i in range(2, max_num + 1): dp[i] = max(dp[i - 1], i * freq[i] + dp[i - 2]) return dp[max_num]
- 复杂度分析
- 时间复杂度：需要遍历数组两次，第一次统计每个数字的出现次数，第二次进行动态规划计算，时间复杂度为 ，其中
n是数组nums的长度，m是数组中的最大数字。 - 空间复杂度：需要创建一个长度为
max_num + 1的数组来存储动态规划的结果，空间复杂度为 ，其中m是数组中的最大数字。
