题目链接
题目描述
实现代码
思路:由题意得知,如果选择元素值x,那么元素值x相邻的两个整数x-1 和 x+1都不能被选取,同时将所有的x选取并删除;因此,我们可以先将数组进行排序,然后将重复元素进行移除并累加,最终得到缩减版的无重复元素的排序数组,然后问题就演变成了打家劫舍;
实现代码如下(这里未使用排序 + dp,直接使用的dp):
class Solution {
public int deleteAndEarn(int[] nums) {
int maxVal = 0;
for (int val : nums) {
maxVal = Math.max(maxVal, val);
}
int[] sum = new int[maxVal + 1];
for (int val : nums) {
sum[val] += val;
}
return rob(sum);
}
public int rob(int[] nums) {
int size = nums.length;
int first = nums[0], second = Math.max(nums[0], nums[1]);
for (int i = 2; i < size; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}