来宾住房与城乡建设网站,如何去做网络推广,高端建筑围护系统,免费建网给你一个整数数组 nums #xff0c;你可以对它进行一些操作。
每次操作中#xff0c;选择任意一个 nums[i] #xff0c;删除它并获得 nums[i] 的点数。之后#xff0c;你必须删除每个等于 nums[i] - 1 或 nums[i] 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作…给你一个整数数组 nums 你可以对它进行一些操作。
每次操作中选择任意一个 nums[i] 删除它并获得 nums[i] 的点数。之后你必须删除每个等于 nums[i] - 1 或 nums[i] 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1
输入nums [3,4,2] 输出6 解释 删除 4 获得 4 个点数因此 3 也被删除。 之后删除 2 获得 2 个点数。总共获得 6 个点数。
解题思路
代码分为两个部分
统计每个元素出现的次数方便计算删除元素后的得分并且找出最大值为了缩小dp数组的长度 for _, num : range nums {cnt[num]if nummax{maxnum}}状态转移 dp[i][0]代表当前元素是i并且不删除该元素。因此前一个元素可以是被删除元素也可以不是 dp[i][1]代表当前元素是i需要删除该元素。因此前一个元素必须不为删除元素因为如果前一个元素是删除元素该元素已经被删除掉了并且加上删除后的得分 for i : 1; i max; i {dp[i][0]MaxV(dp[i-1][0],dp[i-1][1])dp[i][1]dp[i-1][0]i*cnt[i]}代码
func MaxV (a int,b int) int {if ab{return a}else {return b}
}func deleteAndEarn(nums []int) int {cnt:make([]int,10008)max:-1for _, num : range nums {cnt[num]if nummax{maxnum}}dp:make([][2] int,max1)for i : 1; i max; i {dp[i][0]MaxV(dp[i-1][0],dp[i-1][1])dp[i][1]dp[i-1][0]i*cnt[i]}return MaxV(dp[max][0],dp[max][1])
}
