Problem

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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5
6
7

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.

Solution

Method 1 - DP

To solve this problem, we can use a dynamic programming approach similar to the “house robber” problem. Here’s the step-by-step approach:

  1. Count Frequency of Each Element: First, count the total points you would get if you deleted each element independently. This can be done using a frequency array or a dictionary.
  2. Use Dynamic Programming: Create a dp array where dp[i] represents the maximum points that can be earned considering all elements from 0 to i. The dynamic programming transitions are:
    • If you do not choose i, the points are the same as not choosing i-1, i.e., dp[i-1].
    • If you choose i, you add the points from i to the points obtained from i-2, because choosing i requires removing elements i-1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int deleteAndEarn(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        // Calculate the maximum value in nums
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }
        
        // Frequency array
        int[] freq = new int[maxVal + 1];
        for (int num : nums) {
            freq[num] += num;
        }
        
        // DP array
        int[] dp = new int[maxVal + 1];
        dp[1] = freq[1];
        
        for (int i = 2; i <= maxVal; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + freq[i]);
        }
        
        return dp[maxVal];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        max_val = max(nums)
        
        # Frequency array
        freq = [0] * (max_val + 1)
        for num in nums:
            freq[num] += num
            
        # DP array
        dp = [0] * (max_val + 1)
        dp[1] = freq[1]
        
        for i in range(2, max_val + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + freq[i])
            
        return dp[max_val]

Complexity

  • ⏰ Time complexity: O(n + m) where n is the length of the input array nums and m is the range of the numbers in nums. Building the frequency array/dictionary and the dp array takes linear time relative to the range and the number of elements.
  • 🧺 Space complexity: O(m) for the dp array and the frequency count if using a dictionary.