#740
Delete and Earn
specialist · 760 · lc medium +31 · verified · 57.1% accepted · 7,945 likes · top 52%
Description
Given an integer array nums, repeatedly choose a value nums[i] to earn nums[i] points, but doing so forces you to remove all elements equal to nums[i] - 1 and nums[i] + 1 from the array. Return the maximum total points you can accumulate.
Example 1:
Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.
Example 2:
Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.
Code
1
2
3