Get the sum by deleting elements from the array

Problem Statement:

You are given an array, you need to delete the element at nums[i] to earn num[i].
But after every delete, you have to delete all the elements that are equal to num[i] – 1 or num[i] + 1.
You need to return the max sum.

Example

Input: nums = [4,5,3]
Output: 8

First delete 5, so you have to delete 4. Till now earned 5 points.

Then delete 3, you earn “5 + 3 = 8” points.

Solution

This solution can be solved by using DP.

For that we will first see the recurrance relation. Once we form the recurrance relation, it will be easy to perform DP.

This problem can be reduced to house robber problem.

If we understand the problem carefully, then we can deduce below points.

If we take nums[i] then,
we can take all the copies
we cannot take any copies of nums[i-1] and nums[i+1]

So to reduce the problem to house robber problem we can store the occurance of each number in a frequency array and then apply the logic of house robber on the frequency array.

Example: nums = {2, 2, 2, 3, 3, 4, 5, 5}
freq_array = {0, 0, 3, 2, 1, 2}

Below is the solution for Bottom Up approach

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_set> 
#include <list> 

using namespace std;

int delete_and_earn_bottom_up(vector<int>& nums) 
{
    if(nums.size()==0) 
      return 0;

    
    std::vector<int> freq_arr(10001,0); // frequency of numbers from 1 to 10000
    for(int i:nums){
        ++freq_arr[i];
    }
    
    std::vector<int> dp(freq_arr.size()+1,0);
    dp[1]=freq_arr[1]*1;
    
    for(int i=2;i<=10000;++i)
    {
      // at dp[i] we have 2 choices
      // either take the ith value and take dp[i-2]
      // or you can choose dp[i-1]
      // then we need to take the max of both the values
        dp[i]=std::max(dp[i-1],freq_arr[i]*i+dp[i-2]);
    }
    return dp[10000];
}

int main(int argc, char const *argv[])
{
  vector<int> nums = {2, 2, 3, 3, 3, 4};
  cout<<"The max sum after delete is "<< delete_and_earn_bottom_up(nums)<<endl; 
  return 0;
}

Output:

The max sum after delete is 9