给定一个整数数组nums。您希望通过多次执行以下操作来最大化获得的分数：
选择任何nums[i]并删除它以获得nums[i]积分。之后，您必须删除每个等于 的元素nums[i] - 1和每个等于 的元素nums[i] + 1。
通过多次应用上述操作返回您可以获得的最大积分数。
示例 1：
输入： nums = [3,4,2]
输出： 6
解释：您可以执行以下操作：
- 删除 4 获得 4 分。因此，3 也被删除。数字 = [2]。
- 删除 2 获得 2 分。数字 = []。
您总共获得 6 分。
示例 2：
输入： nums = [2,2,3,3,3,4]
输出： 9
解释：您可以执行以下操作： - 删除一个 3 获得 3 分。所有 2 和 4 也被删除。数字 = [3,3]。
- 再次删除 3 即可获得 3 分。数字 = [3]。
- 再次删除 3 以获得 3 分。数字 = []。
您总共获得 9 分。
约束：
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 10^4
运用之前198, 213抢钱的题思路
- 建立一个长度为10001的数组, 因为约束nums中的数在1到10000之间。数组用来记录当前位置有多少个数，例如[2,2,2,3,3,4], 则产生数组为[0,0,3,2,1]因为位置2在nums中的2有3个, 3有2个, 4有1个
- 初始化一个长度10001, 全为-1的数组
- 建立一个函数用来将累积求和的数添加到全为-1的数组中, 这里用到之前抢劫的思路, 当前的只能和隔一位的数加和
class Solution {
public int deleteAndEarn(int[] nums) {
int[] n = new int[10001];
for (int i : nums) {
n[i] += i;
}
return rob(n);
}
static int rob(int[] nums) {
int temp[] = new int[nums.length];
Arrays.fill(temp, -1);
return helper(nums, 0, temp);
}
static int helper(int[] nums, int index, int[] temp) {
if(index>=nums.length) return 0;
if(temp[index]!=-1) return temp[index];
return temp[index] = Math.max(helper(nums, index + 2, temp) + nums[index], helper(nums, index + 1, temp));
}
}
由于初始化两个10000长度数组并且又把他们遍历了一遍最后, 所以时间和空间复杂度都很大
方法2用动态规划Dynamic Programming
- 初始化长度10001的数组, 用来记录每个数出现的次数
- 定义3个变量用来存储当前值cur, 删掉的值del, 前一位的值pre
- 遍历这个长度为10001的数组, 这里可以将条件限制为只有里面的值大于1时才进行下面运算
for(int i=0;i<10001;i++)if(n[i]>0){...}
- 定一个temp用来存储当前最大值Math.max(cur,del) del指的是当前数的前一个数
- 如果当前数的前一位和pre不是一个, 即计数的时候为0, 例如nums=[1,1,2,2,4] count=[0,2,2,0,1], 当i=4时, i-1=3 pre=2
cur=i*count[i]+temp; //i*count[i]表示当前这个数在原数组中有多少个 del=temp;//del用来算i+1时用
- 当i-1=pre时cur=i*count[i]+del
class Solution {
public int deleteAndEarn(int[] nums) {
int[] n = new int[10001];
for (int i : nums) {
n[i]++;
}
int pre=-1,cur=0,del=0;
for (int i = 0; i <= 10000; i++){
if(n[i]>0){
int temp = Math.max(cur, del);
if (i - 1 != pre) {
cur = i * n[i] + temp;
del = temp;
}else{
cur = i * n[i] + del;
del = temp;
}
pre = i;
}
}
return Math.max(cur,del);
}
}
时间复杂度O(nlogn)
