740. Delete and Earn
- since we can only delete the arr[i] - 1 and arr[i] + 1, therefore sorting and counting frequencies it would be a good idea.
- we framed this problem as house robber type, to take or not to take.
- but here if the previous element isn’t the current - 1, then we can take that too, unlike house robber.
how to start
- States
First, we need to decide on state variables. As a reminder, state variables should be fully capable of describing a scenario.
- Recurrence relation
Next, we need to find a recurrence relation, which is typically the hardest part of the problem. For any recurrence relation, a good place to start is to think about a general state
- Base case
- Code it
you might want to solve House robber first.
implementation
```cpp
class Solution {
public:
int deleteAndEarn(vector& nums) {
using ll = long long int;
map<ll, ll> mp;
for (const auto& i: nums) mp[i] ++;
sort(nums.begin(), nums.end());
nums.resize(unique(nums.begin(), nums.end()) - nums.begin());
ll n = nums.size();
vector dp(n + 1, 0);
dp[0] = nums[0] * mp[nums[0]];
if (n == 1) return dp[0];
if (nums[1] == nums[0] + 1)
dp[1] = max(dp[0], mp[nums[1]] * nums[1]);
else
dp[1] =(dp[0] + mp[nums[1]] * nums[1]);
for (int i = 2; i < n; i++) {
if (nums[i] == nums[i - 1] + 1)
dp[i] = max(dp[i - 2] + nums[i] * mp[nums[i]], dp[i - 1]);
else
dp[i] = max(dp[i - 2], dp[i - 1]) + nums[i] * mp[nums[i]];
}
return dp[n - 1];
}
};
```
</details>