Array     C++     Dynamic Programming     Hash Table     Medium    

Problem Statement:

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

  • Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.

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:

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 104

Solution:

Notice that whichever number you choose to earn, you can earn all instances of that number and none of the number to the left or right. Hence, we need to find the frequency or rather the total points possible for earning each number and then run a House Robber on that.

House robber can be solved using DP. Here I have given two ways to solve it: using a DP array or using just two integer variables.

 
class Solution {
public:
    int rob_v1(vector<int> money)
    {
        int n=money.size();
        if (n==1) return money[0];
        vector<int> dp(n,0);
        dp[0] = money[0]; dp[1] = max(money[0], money[1]);
        for (int i=2; i<n; i++) dp[i] = max(dp[i-2]+money[i], dp[i-1]);
        return dp[n-1];
    }
    
    int rob_v2(vector<int>  money)
    {
        int n=money.size();
        if (n==1) return money[0];
        int a=money[0], b=max(money[0], money[1]), b_old;
        for (int i=2; i<n; i++)
        {
            b_old = b;
            b = max(a+money[i], b);
            a = b_old;
        }
        return b;
    }
    int deleteAndEarn(vector<int>& nums) {
        int maxNum = 10000;
        vector<int> points(maxNum, 0);
        for (int n: nums) points[n-1]+=n;
        return rob_v2(points);
    }
};