遵义网站制作如何收费,机关网站建设引导语,定制衣服app软件哪个好,淄博网站设计丨致信网络题目描述#xff1a;
给你一个整数数组 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 个点数。示例 2
输入nums [2,2,3,3,3,4]
输出9
解释
删除 3 获得 3 个点数接着要删除两个 2 和 4 。
之后再次删除 3 获得 3 个点数再次删除 3 获得 3 个点数。
总共获得 9 个点数。提示
1 nums.length 2 * 1041 nums[i] 104 思路
根据题目意思我们可以很容易得到如果我们要选择删除x,那么我们会将所有的x1和x-1的元素全部删掉并获得x点数换句话说我们选择不能同时同时获得x和x1点数或者是x和x-1点数。因为如果获得了x点数x1的元素与x-1的元素就已经全部不存在了而如果有多个x,我们就可以获得这些x总和的点数。
我们可以用sum[x]表示元素x的总和点数。
那么这个题和打家劫舍就一样了求不能选相邻元素的最大点数。
转化成为背包的思想--选或者不选 选x就要加上所有x总和的点数这个状态是由x-2转移过来的 不选x,那么上一个状态就是x-1 用f[x]表示在0--x里面选不相邻的值获得的最大点数。 f[x]max(f[x-1],f[x-2]sum[x]) 代码
class Solution {
public:int deleteAndEarn(vectorint nums) {int lennums.size();int max_v0;//记录nums数组里最大的数也就是数组sum的下标范围for(int i0;ilen;i){if(nums[i]max_v){max_vnums[i];}}vectorint sum(max_v10,0);for(int i0;ilen;i){sum[nums[i]]nums[i];//sum[nums[i]]表示值为nums[i]的总和}vectorint f(max_v1,0);f[0]sum[0];f[1]max(sum[1],sum[0]);for(int i2;imax_v;i){f[i]max(f[i-1],f[i-2]sum[i]);}return f[max_v];}
};
