Delete and Earn

Problem Statement

In this problem, you are provided with an array of integers named nums. Your objective is to maximize the number of points you accumulate by repeatedly performing a specific operation. The operation involves selecting an item nums[i] from the array, deleting it, and earning points equal to the value of nums[i]. However, the operation comes with a constraint: upon picking and deleting nums[i], every other element in the array that has a value of either nums[i]-1 or nums[i]+1 must also be deleted immediately, although they do not contribute to the point score. The challenge is to determine the maximum total points that can be achieved by applying this operation as many times as needed. The problem demands a solution that does not simply involve maximizing point gain in each step but rather maximizing the total gain by strategically choosing elements for deletion, accounting for their surrounding impacts.

Examples

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

Approach and Intuition

The key to solving this problem efficiently lies in recognizing that it resembles the "house robber" problem, where one cannot rob two adjacent houses. Here, points from two adjacent numbers in sorted order cannot be taken together.

1. Dynamic Programming for Optimized Point Collection:

   • Convert the task into a dynamic programming problem where the state represents the maximum points obtainable from the first i unique numbers.
   • Utilize a hashmap or an array to keep track of the total points available from each unique number in nums by summing occurrences of each number.
   • Create a DP array dp where dp[i] will represent the maximum score obtainable using numbers from 1 to i.

2. Base Cases and Transitions:

   • If only one number is available (k), then the maximum points are simply the total value of all occurrences of that number.
   • For each number k encountered in nums, relate its value to either taking k (and not taking k-1) or not taking k at all. This relationship is described by the equation:
     • dp[k] = max(dp[k-1], dp[k-2] + k * count[k]) Where dp[k-1] is the maximum points without taking k and dp[k-2] + k * count[k] symbolizes taking the k value into account along with the points from k taking its frequency into consideration and excluding k-1.

3. Iterating through Possibilities:

   • To ensure all bases are covered, iterate from the lowest to the highest number found in nums, applying the above recurrence to fill the dp array.

4. Return the Result:

   • The answer to the problem would then be found in dp[x] where x is the maximum value in nums.

By following this approach, where we use dynamic programming to balance between choosing numbers and maximizing points, we can efficiently achieve the solution to the problem, even for large arrays. The examples provided illustrate how this strategy plays out with different configurations of nums.

Solutions

class Solution {
    public int removeAndProfit(int[] elements) {
        int highestValue = 0;
        HashMap<Integer, Integer> valueMap = new HashMap<>();
    
        for (int element : elements) {
            valueMap.put(element, valueMap.getOrDefault(element, 0) + element);
            highestValue = Math.max(highestValue, element);
        }
    
        int prevPrevMax = 0;
        int prevMax = 0;
        int n = valueMap.size();
    
        if (highestValue < n + n * Math.log(n) / Math.log(2)) {
            prevMax = valueMap.getOrDefault(1, 0);
            for (int curr = 2; curr <= highestValue; curr++) {
                int temp = prevMax;
                prevMax = Math.max(prevMax, prevPrevMax + valueMap.getOrDefault(curr, 0));
                prevPrevMax = temp;
            }
        } else {
            List<Integer> sortedKeys = new ArrayList<Integer>(valueMap.keySet());
            Collections.sort(sortedKeys);
            prevMax = valueMap.get(sortedKeys.get(0));
    
            for (int i = 1; i < sortedKeys.size(); i++) {
                int key = sortedKeys.get(i);
                int tmp = prevMax;
                if (key == sortedKeys.get(i - 1) + 1) {
                    prevMax = Math.max(prevMax, prevPrevMax + valueMap.get(key));
                } else {
                    prevMax += valueMap.get(key);
                }
    
                prevPrevMax = tmp;
            }
        }
    
        return prevMax;
    }
}