Approach #1: Dynamic Programming [Accepted]
Intuition
Because all numbers are positive, if we "take" a number (use it to score points), we might as well take all copies of it, since we've already erased all its neighbors. We could keep a count of each number so we know how many points taking a number is worth total.
Now let's investigate what happens when we add a new number X
(plus copies) that is larger than all previous numbers. Naively, our answer would be the previous answer, plus the value of X
 which can be solved with dynamic programming. However, this fails if our previous answer had a number taken that was adjacent to X
.
Luckily, we can remedy this. Let's say we knew using
, the value of our previous answer, and avoid
, the value of our previous answer that doesn't use the previously largest value prev
. Then we could compute new values of using
and avoid
appropriately.
Algorithm
For each unique value k
of nums
in increasing order, let's maintain the correct values of avoid
and using
, which represent the answer if we don't take or take k
respectively.
If the new value k
is adjacent to the previously largest value prev
, then the answer if we must take k
is (the point value of k) + avoid
, while the answer if we must not take k
is max(avoid, using)
. Similarly, if k
is not adjacent to prev
, the answer if we must take k
is (the point value of k) + max(avoid, using)
, and the answer if we must not take k
is max(avoid, using)
.
At the end, the best answer may or may not use the largest value in nums
, so we return max(avoid, using)
.
Our demonstrated solutions showcase two different kinds of sorts: a library one, and a radix sort. For each language, the other kind of solution can be done without much difficulty, by using an array (Python) or HashMap (Java) respectively.
Complexity Analysis

Time Complexity (Python): , where is the length of
nums
. We make a single pass through the sorted keys of , and the complexity is dominated by the sorting step. 
Space Complexity (Python): , the size of our
count
. 
Time Complexity (Java): We performed a radix sort instead, so our complexity is where is the range of allowable values for
nums[i]
. 
Space Complexity (Java): , the size of our
count
.
Analysis written by: @awice.