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
Input:
nums = [3,4,2]Output:
6Explanation:
Delete 4 to earn 4 points. Delete 2 to earn 2 points. Total: 6.
Input:
nums = [1,1,1,2,4,5,5,5,6]Output:
18Explanation:
It 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.
Input:
nums = [10,12,7,9,14]Output:
43Explanation:
The optimal non-adjacent value selection totals 43, so the answer is 43.
Constraints
- •
1 ≤ nums.length ≤ 2 × 10⁴ - •
1 ≤ nums[i] ≤ 10⁴