Delete and Earn
You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:
- Pick any
nums[i]and delete it to earnnums[i]points. Afterwards, you must delete every element equal tonums[i] - 1and every element equal tonums[i] + 1.
Return the maximum number of points you can earn by applying the above operation some number of times.
Example 1
Input
nums = [3,4,2]Output
6Deleting 4 earns 4 points and removes 3, then deleting 2 earns 2 more points for a total of 6.
Example 2
Input
nums = [2,2,3,3,3,4]Output
9Deleting all three 3s earns 9 total points, while all 2s and 4 are removed after the first 3 is deleted.
Constraints
- 1 <= nums.length <= 2 * 10^4
- 1 <= nums[i] <= 10^4