Delete And Earn - Leetcode Solution

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: 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.

Solution: For this problem, we need to find the maximum point that can be earned by deleting elements from the given array. We start by looping through the array to get the frequency of each element in the array and storing it in a dictionary.

We then create a list dp of size equal to the maximum element in the array + 1 and initialize all its values to zero. dp[i] represents the maximum point that can be earned by deleting all elements up to i.

To find dp[i], we have two options:

1. Delete the i-th element and all elements equal to nums[i] - 1 and nums[i] + 1. The total points earned would be nums[i] + dp[nums[i]-2].
2. Skip the i-th element and the points earned would be dp[i-1].

We take the maximum of the above two options and store it in dp[i]. Finally, we return the last element of the dp list, which gives us the maximum points that can be earned.

Here is the Python implementation of the above algorithm:

def deleteAndEarn(nums: List[int]) -> int: freq = {} for num in nums: freq[num] = freq.get(num, 0) + 1

max_num = max(nums)
dp = [0]*(max_num+1)
for i in range(1, max_num+1):
    # Option 1: delete i and all i-1 and i+1 elements
    if i in freq:
        points_with_i = i*freq[i]
        if i-2 >= 0:
            points_with_i += dp[i-2]
        dp[i] = max(dp[i], points_with_i)

    # Option 2: skip i
    dp[i] = max(dp[i], dp[i-1])

return dp[max_num]

1