# 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⁴</code>
- <code>1 <= nums[i] <= 10⁴</code>

## Solution 1
#### C++

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
打家劫舍系列, 將一樣分數的合在一起變成價值較高的房子