wordpress关闭邮件验证,怎么优化网站内容,wordpress 修改自定义菜单,小女孩做网站740. 删除并获得点数#xff08;leetcode#xff09;
题目描述 给你一个整数数组 nums #xff0c;你可以对它进行一些操作。每次操作中#xff0c;选择任意一个 nums[i] #xff0c;删除它并获得 nums[i] 的点数。之后#xff0c;你必须删除 所有 等于 nums[i] - 1 和 …740. 删除并获得点数leetcode
题目描述 给你一个整数数组 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 n u m s . l e n g t h 2 ∗ 1 0 4 1 nums.length 2 * 10^4 1nums.length2∗104 1 n u m s [ i ] 1 0 4 1 nums[i] 10^4 1nums[i]104 题解1C版本
class Solution {
public:int deleteAndEarn(vectorint nums) {mapint,int mp; // 由于map默认是按key从小到大排序的因此用key表示nums[i], value表示数组nums中所有等于nums[i]的元素之和for(int i 0; i nums.size(); i) {if(!mp.count(nums[i])){mp[nums[i]] nums[i];}else mp[nums[i]] nums[i];}vectorvectorint dp(mp.size() 1, vectorint(2, 0)); // dp[i][0]表示以mp中第i个元素结尾且选中第i个元素的获得的最大点数// dp[i][1]表示以mp中第i个元素结尾但不选中第i个元素的获得的最大点数int last 0, i 0; // last表示上一个元素的值 for(auto m : mp){i;if(m.first ! last 1) { // 后一个元素不等于前一个元素加1可以选当前元素dp[i][0] max(dp[i - 1][1], dp[i - 1][0])m.second;}else { // 后一个元素等于前一个元素加1不可以选当前元素dp[i][0] dp[i - 1][1] m.second;}dp[i][1] max(dp[i - 1][0], dp[i - 1][1]);last m.first;}return max(dp[mp.size()][0], dp[mp.size()][1]);}
};
