Delete and Earn

Problem

You are given an integer array nums. You repeatedly perform the following operation until the array is empty: pick any element with value v, gain v points, and remove that element; at the same time, every element equal to v - 1 and every element equal to v + 1 is removed from the array without earning anything. Return the maximum number of points you can earn.

• nums holds up to about twenty thousand positive integers, each no larger than about ten thousand.

Examples

• nums = [5, 6, 4] → 10. Take 6 and 4 (removing the 5). Taking 5 first would destroy both neighbors and leave only 5 points.
• nums = [3, 3, 4, 4, 4, 5] → 12. Take all three 4s (removing the 3s and the 5) for 12. Taking the 3s and the 5 gives only 11.
• nums = [7] → 7. One element, one point.

Hints

1. Once you take one copy of value v, is there any reason not to take every other copy of v? What does that tell you about the decision per value?
2. Group the points by value: gain[v] = v * count(v). Which values conflict with each other?
3. This is the no-two-adjacent-picks DP (House Robber) over consecutive values instead of positions.