You have a bag of n positive integers (values may repeat). One move works like this: choose any value v still in the bag, earn v multiplied by the number of copies of v currently present, then remove every copy of v and every copy of v-1 and v+1 from the bag. Keep making moves until the bag is empty.
Return the maximum total points you can earn.
Line 1: an integer n, the number of values.
Line 2: n space-separated positive integers.
A single integer: the maximum total points.
Example 1
Input
6 2 2 3 3 3 4
Expected
9
Explanation
Taking value 3 earns 3*3 = 9 but deletes the 2s and 4s. Taking 2 and 4 instead earns 2*2 + 4*1 = 8. The best is 9.
Example 2
Input
3 1 1 1
Expected
3
Explanation
Only the value 1 is present; taking it earns 1*3 = 3, which is the whole bag.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →