# 740. Delete and Earn

Given an array `nums` of integers, you can perform operations on the array.

In each operation, you pick any `nums[i]` and delete it to earn `nums[i]` points. After, you must delete everyelement equal to `nums[i] - 1` or `nums[i] + 1`.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

``````Input: nums = [3, 4, 2]
Output: 6
Explanation:
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.
``````

Example 2:

``````Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation:
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.
``````

Note:

• The length of `nums` is at most `20000`.
• Each element `nums[i]` is an integer in the range `[1, 10000]`.

``````class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
vector<int> sums(10001, 0);
int take = 0, skip = 0;
for (int num : nums) sums[num] += num;
for (int i = 0; i < 10001; ++i) {
int takei = skip + sums[i];
int skipi = max(skip, take);
take = takei; skip = skipi;
}
return max(skip, take);
}
};
``````

``````class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
vector<int> sums(10001, 0);
for (int num : nums) sums[num] += num;
for (int i = 2; i < 10001; ++i) {
sums[i] = max(sums[i - 1], sums[i - 2] + sums[i]);
}
return sums[10000];
}
};
``````

House Robber

https://discuss.leetcode.com/topic/112807/java-c-clean-code-with-explanation

https://discuss.leetcode.com/topic/112916/sharing-my-simple-straight-forward-java-o-n-solution-explanation-included

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation