题目描述

链接: https://leetcode-cn.com/problems/delete-and-earn/

给你一个整数数组nums, 可以对他进行一些操作. 每次操作中, 选择任意一个nums[i], 删除它然后获取nums[i]的点数. 同时还需要删除所有 等于nums[i]-1和nums[i]+1的元素. 例如删除3, 那么得到3个点数, 同时需要在数组中删除所有的2和4.

开始时拥有0个点数, 求你能通过这些操作获取的最大点数.

示例1:

输入: nums = [3, 4, 2]

输出: 6

删除4和2.得到6点.

删除4获取4个点数, 同时3也被删除.

还剩下2, 然后删除2再得到2个点数.

示例2:

输入: nums = [2, 2, 3, 3, 3, 4]

输出: 9

删除3, 总共可以得到9个点数(3*3). 同时删除2和4.

最终得到9个点数.

解题思路

删除nums[i]时, 需要将num[i]-1和nums[i]+1一起删除掉. 并且如果nums[i]在数组中有多个值, 我们可以得到nums[i]多个值的和.

我们先将题目进行一次转化, 输入[2, 2, 3, 3, 3, 4]

将nums[i]放到newArray[nums[i]]的位置并进行累积. 这里只有2, 3, 4三个元素. 则分别放到相应的文件然后进行累加. 转化为 [0, 0 ,4, 9, 4].

然后我们再来看一下这个问题, 我们在newArray中, 得到newArray[i]时, 就无法得到newArray[i-1]和newArray[i+1].

这个问题与打家劫舍问题类型.

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int deleteAndEarn(int[] nums) {
   		int max = Integer.MIN_VALUE;
	    		for (int num : nums) {
   		    					if (num > max) {
       				    						max = num;
   					    		}
   				}
   				int[] sum = new int[max + 1];
   				for (int num : nums) {
   		    					sum[num] = sum[num] + num;
   				}
   				int x = sum[0], y = Math.max(sum[0], sum[1]);
   				for (int i = 2; i < sum.length; i++) {
   		    					int temp = y;
   		    					y = Math.max(x + sum[i], y);
   		    					x = temp;
   				}
   				return y;
}

相关题目