Delete and Earn
Medium · dynamic programming
A game table holds tiles, each showing a whole number. The list nums gives the number on every tile.
On each turn you pick one tile, score the number on it, and then every tile showing one less or one more than the number you picked is thrown away. Tiles showing the same number as the one you picked stay on the table, so you can pick them on later turns.
Keep playing for as many turns as you like. Return the largest total score you can reach.
Examples
Example 1
Input: nums = [3, 4, 2]
Output: 6
Pick 4 (score 4), which throws away the 3. Then pick 2 (score 2). Total 6.
Example 2
Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Pick a 3 three times for 9 points. Taking the 2s and the 4 instead gives only 2 + 2 + 4 = 8.
Example 3
Input: nums = [5]
Output: 5
Constraints
- 1 <= len(nums) <= 2 * 10^4
- 1 <= nums[i] <= 1000