Delete and Earn

Problem Description

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.

Key Insights

• The problem can be viewed as a variation of the "House Robber" problem, where you cannot choose adjacent elements.
• The value earned from deleting a number is equal to the number itself multiplied by its frequency in the array.
• The optimal solution involves calculating the maximum points that can be earned by deciding whether to include or exclude each number, while considering the constraints imposed by the adjacent numbers.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of the input array and m is the range of numbers (up to 10,000). Space Complexity: O(m), where m is the range of numbers, used for storing the points for each number.

Solution

To solve the problem, we first create an array to count the frequency of each number from the input array. Then, we transform this frequency into a points array where each index represents the number and the value at that index represents the total points that can be earned by picking that number. We then apply a dynamic programming approach similar to the "House Robber" problem, where for each number, we decide whether to take the points or skip to avoid adjacent conflicts.

Code Solutions