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.

&nbsp;
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.

&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 2 * 104
	1 &lt;= nums[i] &lt;= 104


class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        count = Counter(nums)
        m = max(nums)
        memo = {}
        def choose(num):
            if num > m:
                return 0
            if num not in count:
                count[num] = 0
            if num in memo:
                return memo[num]
            memo[num] = max(choose(num + 1), num * count[num] + choose(num + 2))
            return memo[num]
        
        return choose(1)

# time and space complexity
# n = max(nums)
# time: O(n)
# space: O(n)
            
            
class Solution {
    public int deleteAndEarn(int[] nums) {
        Arrays.sort(nums);
        int onePreviousAgo = 0;
        int previous = 0;
        for(int i = 0; i < nums.length; i++) {
            int sum = 0;
            // On hop there's no constraint to add the previous value
            if(i > 0 && nums[i-1] < nums[i] - 1) {
                onePreviousAgo = previous;
            }
            // Accumulate equal values
            while(i < nums.length - 1 && nums[i] == nums[i+1]) {
                sum += nums[i];
                i++;
            }
            int currentPrevious = previous;
            previous = Math.max(
                onePreviousAgo + nums[i] + sum,
                previous
            );
            onePreviousAgo = currentPrevious;
            // System.out.println(nums[i] + ":" + previous);
        }
        return previous;
    }
}
class Solution {
public:
    // Dynamic Programming : Bottom Up Approach Optmised
    int deleteAndEarn(vector<int>& nums)
    {
        int size = nums.size();

        // Initialise vectors with size 10001 and value 0
        vector<int> memo(10001 , 0);
        vector<int> res(10001 , 0);

        // get the count of elements int res vector
        for(auto num : nums)
            res[num]++;

        // for index : less than 3 calculate memo[i] as the index times number of occurences
        // : greater than equal to 3 as calculate memo[i] as the index times number of occurences + max of the last second and third element
        for(int i = 0 ; i < 10001 ; i++)
            memo[i] += (i < 3) ? (i * res[i]) : (i * res[i]) + max(memo[i-2] , memo[i-3]);

        // return max of last 2 elements
        return max(memo[10000] , memo[9999]);
    }
};
var deleteAndEarn = function(nums) {
    let maxNumber = 0;
    
    const cache = {};
    const points = {};

    function maxPoints(num) {
        if (num === 0) {
            return 0;
        }
        
        if (num === 1) {
            return points[1] || 0;
        }
        
        if (cache[num] !== undefined) {
            return cache[num];
        }
        
        const gain = points[num] || 0;
        return cache[num] = Math.max(maxPoints(num - 1), maxPoints(num - 2) + gain);
    }
    
    for (let num of nums) {
        points[num] = (points[num] || 0) + num;
        maxNumber = Math.max(maxNumber, num);
    }

    return maxPoints(maxNumber);
};
Delete and Earn