Delete and earn: most points when taking a value deletes its neighbors

You are given an integer array. Taking an element with value x earns x points and deletes every element equal to x - 1 or x + 1. You may keep taking elements until none remain. Return the most points you can earn.

Interface

Unless you agree on a different interface with the interviewer, assume:

• delete_and_earn(nums: list[int]) -> int

Example

delete_and_earn([3, 4, 2])                     ->  6    # take 4 (deletes 3), then 2
delete_and_earn([2, 2, 3, 3, 3, 4])            ->  9    # take all three 3s; 2s and 4s are deleted
delete_and_earn([1, 1, 1, 2, 4, 5, 5, 5, 6])   ->  18   # three 1s, then three 5s

Constraints

• 1 <= len(nums) <= 2 * 10^4
• 1 <= nums[i] <= 10^4; values can be sparse and repeated.

Clarifying questions

• Can values be zero or negative?
• How large is the value range compared with the array length?
• Do I need the chosen values, or only the score?

What a strong answer covers

• Once you take one copy of x, its neighbours are gone, so you take every copy: the gain for value x is x * count(x).
• The reduction to house robber over values: adjacent values conflict, so best(v) = max(best(v - 1), best(v - 2) + gain(v)).
• Handling sparse values by walking the sorted distinct values and resetting the "adjacent" rule across gaps, giving O(n + d log d) instead of O(max value).
• O(1) extra state beyond the counts.
• Tests: one distinct value, consecutive runs, values with gaps.

Follow-ups

• Values range up to 10^9: what changes?
• Taking x deletes everything within distance d, not just 1.
• Return which values to take.
• Negative values are allowed; does the greedy "take every copy" still hold?