Delete and Earn
Medium · Dynamic Programming · about 20 minutes
Asked at Amazon, Microsoft, Salesforce, ByteDance, Bloomberg.
You play a game on nums. A move chooses some remaining value x, scores x points, removes that copy of x, and also removes every remaining copy of x - 1 and x + 1. Play as long as you like; what's the highest score you can collect?