413. Delete a Value and Earn
Pick any value from the list and earn that value, but doing so deletes EVERY copy of it along with every copy of the values one above and one below. Repeat until the list is empty. Print the most that can be earned.
2 2 3 3 3 4 -> 9 take every 3, losing all 2s and the 4
The description invites simulation, and simulation is the wrong shape entirely: the order of picks does not matter, only which VALUES are taken.
Notice what the deletion rule really says. Taking value v earns v times its
count, and forbids taking v-1 and v+1. Nothing else is affected.
So group by value and lay the values out on a number line. The question becomes:
choose values, no two adjacent ON THE NUMBER LINE, maximising the sum of
v * count(v). That is problem #451 exactly, over the value axis rather than the
input order.
gain[v] = v * count(v)
dp[v] = max( dp[v-1], dp[v-2] + gain[v] )
The transformation is the whole problem, and it is the most useful thing here: recognising a known problem after a change of coordinates is worth more than any individual recurrence.
Values with count 0 still occupy a slot, with gain 0, which is what keeps non-adjacent values from being treated as adjacent.
Constraints - `1 ≤ n ≤ 20000` - `1 ≤ value ≤ 10000`
Input
The first line contains an integer n.
The second line contains n space-separated positive integers.
Output
Print the largest total that can be earned.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.