Delete and earn
Group numbers by value first, and the problem becomes House robber over the value line instead of the array. About 12 minutes.
Take a number, lose its neighbours
You have a bag of numbered tokens. Pick a value and you earn that much for every token with that value, but then all tokens one higher and one lower are thrown away.
First, notice that if you take a value at all, you should take every copy of it: copies of the same value never block each other. So what really matters for each value is its total: the value times how many copies there are.
Each value's total is the value times its copies: one 2, one 3 and one 4 here. Taking a value throws away its neighbours, just like robbing a house blocks the houses next door.
This is the robber in disguise
Line the totals up by value: the total for 1, for 2, for 3, and so on. Taking a value blocks the values right next to it, exactly like robbing a house blocks the houses next door.
So once the totals are laid out in a row, the House robber walk solves it unchanged. Tokens 3, 4 and 2 give totals 2, 3 and 4 for the values 2, 3 and 4. Taking 2 and 4 earns 6, the best you can do.
points = [0] * (max(nums) + 1)
for x in nums:
points[x] += x
prev, best = 0, 0
for p in points:
take = prev + p
prev, best = best, max(best, take)
return bestThe tokens are 2, 2, 3, 3, 3. What do you earn in total if you pick the value 3?
- A9
- B3
Show the answer
9. All three 3s are taken together: 3 + 3 + 3 = 9.
Delete and earn
Given an array nums of positive integers, repeatedly choose a number from it: doing so earns you that number's value for every occurrence of it currently in the array, but then every occurrence of value-1 and value+1 must be permanently removed. Return the maximum total points obtainable.
nums = [3, 4, 2] → 6
1 ≤ nums.length ≤ 1,000 · 1 ≤ nums[i] ≤ 1,000