---
# System prepended metadata

title: LC 740. Delete and Earn
tags: [medium, leedcode, DP, c++]

---

# LC 740. Delete and Earn

### [Problem link](https://leetcode.com/problems/delete-and-earn/)

###### tags: `leedcode` `medium` `c++` `DP`

You are given an integer array <code>nums</code>. You want to maximize the number of points you get by performing the following operation any number of times:

- Pick any <code>nums[i]</code> and delete it to earn <code>nums[i]</code> points. Afterwards, you must delete  **every**  element equal to <code>nums[i] - 1</code> and  **every**  element equal to <code>nums[i] + 1</code>.

Return the  **maximum number of points**  you can earn by applying the above operation some number of times.

**Example 1:** 

```
Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.
```

**Example 2:** 

```
Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.
```

 **Constraints:** 

- <code>1 <= nums.length <= 2 * 10<sup>4</sup></code>
- <code>1 <= nums[i] <= 10<sup>4</sup></code>

## Solution 1
#### C++
```cpp=
class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        unordered_map<int, int> umap;
        for (int& num: nums) {
            umap[num]++;
        }

        vector<pair<int, int>> a(umap.begin(), umap.end());
        sort(a.begin(), a.end());
        int n = a.size();
        vector<int> dp(n + 1, 0);

        for (int i = 0; i < n; i++) {
            auto& [num, cnt] = a[i];
            int j = i;
            while (j > 0 && a[j - 1].first >= num - 1) {
                j--;
            }
            dp[i + 1] = max(dp[i], dp[j] + num * cnt);
        }
        return dp.back();
    }
};
```

>### Complexity
>n = nums.length
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(nlogn)        | O(n)             |

## Note
打家劫舍系列, 將一樣分數的合在一起變成價值較高的房子
