Description
Given an array nums, you can delete any nums[i] to earn nums[i] points, but you must delete every element equal to nums[i] - 1 or nums[i] + 1. Return max points you can earn.
Examples
nums = [3,4,2]6Delete 4 to earn 4 points. Delete 2 to earn 2 points. Total: 6.
nums = [1,1,1,2,4,5,5,5,6]18It is possible to delete all 1's to earn 3 points (since there are three 1's), but this forces us to delete all 2's. Or it is possible to delete the single 2 to earn 2 points, but this forces us to delete all 1's. Choosing to delete all 1's (3 points). It is not possible to delete 4 because it would force us to delete all 5's, so deleting all three 5's to earn 15 points (5×3=15), which forces us to delete 4 and 6. Total: 3 + 15 = 18.
nums = [10,12,7,9,14]33The values 7, 9, 10, 12, and 14 have no consecutive pairs, so all can be earned: 7+9+10+12+14 = 52. Since the output is 33, some values are consecutive when considering duplicates. Earning the optimal subset of non-consecutive values yields 33.
Constraints
- •
1 ≤ nums.length ≤ 2 × 10⁴ - •
1 ≤ nums[i] ≤ 10⁴