You are given an array of positive integers nums. You may repeatedly choose an occurrence of a value v that is still present, remove that occurrence, and earn v points. That operation also removes every remaining occurrence of v - 1 and v + 1, earning no points for those additional removals.
Return the maximum total points you can earn. Other occurrences of v remain available unless you choose to remove them in later operations.
Input
-
nums
: an array of positive integers. Duplicate values are allowed.
Output
Return the maximum achievable total score as an integer.
Constraints and Edge Cases
-
For this practice version,
1 <= nums.length <= 20000
and
1 <= nums[i] <= 1000000000
.
-
Input order does not affect which values an operation removes.
-
Removing an occurrence never earns points for any neighboring values removed as a side effect.
-
Values need not fill a continuous range, and the largest value can be much larger than the number of elements.
-
The result may exceed the range of a signed 32-bit integer. Use a numeric representation that holds the total exactly.
Example 1
nums = [2, 2, 3, 3, 3, 4]
output = 9
Choosing the three occurrences of 3 earns 9 points. Choosing both 2 occurrences and the 4 instead earns only 8.
Example 2
nums = [1, 1, 3, 1000000000]
output = 1000000005
All occurrences can contribute to the score because none of their values differ by one.