删除并获得点数

本文主要是介绍删除并获得点数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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.length <= 2 * 104
• 1 <= nums[i] <= 104

class Solution {public int deleteAndEarn(int[] nums) {if(nums.length == 1)return nums[0];Arrays.sort(nums);//排序确定确定要删的位置int num = nums[0],sum = 0;List<Integer> arr = new ArrayList<>();for(int i : nums){if(num==i){//将相同的数加上，因为题意是要删一起删sum+=i;}else{arr.add(sum);//在集合中加上if(num+1!=i){arr.add(0);//如果此值不为连续，像是{1，3，5}，就要在其中插0以分割}num = i;//此时已经是下一个值了{1，1，1，2，2}相当于到了2sum=0;//重新计算和sum+=num;//并在这里加上，因为现在已经遍历到2了，如果不加就会少2}}arr.add(sum);//把最后的加上去，因为在之前的for中无法将最后的sum加入到集合中//现在题目就变为和打家劫舍一样的题目了，不能取相邻的元素if(arr.size()==1)return arr.get(0);int[] dp = new int[arr.size()];dp[0] = arr.get(0);dp[1] = Math.max(arr.get(0),arr.get(1));for(int i = 2;i < arr.size();i++){dp[i] = Math.max(dp[i-1],dp[i-2]+arr.get(i));}return dp[arr.size()-1];}
}

这篇关于删除并获得点数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---