488. Delete and Earn
You are given an array of integers nums. A move works like this: pick one element whose value is v, bank v points, remove that single copy from the array — and every element equal to v - 1 or v + 1 vanishes along with it. Other copies of v are untouched. You keep making moves until the array is empty. Return the maximum number of points you can bank.
Notice what the rule really means: once you take a v, the neighboring values v - 1 and v + 1 are gone forever, but the remaining copies of v are still sitting there, free to be taken on later moves. So the real decision is made per value, not per element — commit to a value and you collect v × (number of copies), at the cost of everything worth v - 1 or v + 1.
Example 1:
Input: nums = [3, 4, 2]
Output: 6
Explanation: Take the 4: it earns 4 points and wipes out the 3. Only the 2 remains; take it for 2 more. Total 4 + 2 = 6. (Taking the 3 first would destroy both the 2 and the 4, leaving just 3 points.)
Example 2:
Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: Take a 3: the two 2s and the 4 all vanish, but the other two 3s survive. Take them on the next two moves. Total 3 + 3 + 3 = 9.
Constraints:
- 1 ≤ nums.length ≤ 2 * 10⁴
- 1 ≤ nums[i] ≤ 10⁴
Hints:
Taking one copy of v never hurts the other copies of v — only values v−1 and v+1 get destroyed. So group the array by value: choosing value v is worth v × count[v] points.
After grouping, the rule is exactly House Robber: you cannot take two adjacent values. Sort the distinct values and decide take/skip for each one.
Watch for gaps. If the next distinct value is not exactly prev + 1, it does not conflict with prev at all — both can be taken freely.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 4, 2]
Expected output: 6