Delete Numbers to Earn Maximum Points
Given a list of integers nums, perform any number of deletion operations to earn the maximum possible points.
In one operation, choose an occurrence of a value x and delete it to earn x points. You must then delete every remaining occurrence of x - 1 and x + 1 without earning points for them.
Return the maximum total points that can be earned. You begin with 0 points.
Method Signature
int deleteAndEarn(List<Integer> nums)
Parameters
nums contains the positive integer values available for deletion.
Return Value
- Return the maximum number of points that can be earned.
Constraints
1 <= nums.size() <= 20,0001 <= nums.get(i) <= 10,000
Example 1
deleteAndEarn(nums = [1, 1, 2, 4, 4, 5])
Output: 10
Delete both occurrences of 1 to earn 2 points and both occurrences of 4 to earn 8 points. These choices do not conflict, giving 10 points in total.
Example 2
deleteAndEarn(nums = [5, 5, 5, 6, 7, 7])
Output: 29
Delete the three occurrences of 5 for 15 points and the two occurrences of 7 for 14 points. The value 6 is removed, producing a maximum total of 29 points.