Delete And Earn

Medium Topics Company Tags

Choose a value from nums, remove one occurrence, and earn that many points. The operation also removes every occurrence of the values one smaller and one larger, without earning points for them. Repeat as desired and return the greatest total score.

Example 1:

Input: nums = [1,1,2,3]

Output: 5

Explanation: Choose both occurrences of 1 and the value 3, earning 1 + 1 + 3 = 5. Choosing 1 removes the 2, but does not remove the 3.

Example 2:

Input: nums = [2,4,6]

Output: 12

Explanation: No two values differ by 1, so all can be chosen. The score is 2 + 4 + 6 = 12.

Example 3:

Input: nums = [5]

Output: 5

Explanation: Choose the only entry to earn 5 points.

Constraints:

  • 1 <= nums.length <= 20000
  • 1 <= nums[i] <= 10000


Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.