Approach #1: Dynamic Programming [Accepted]
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
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
For each unique value
nums in increasing order, let's maintain the correct values of
using, which represent the answer if we don't take or take
If the new value
k is adjacent to the previously largest value
prev, then the answer if we must take
(the point value of k) + avoid, while the answer if we must not take
max(avoid, using). Similarly, if
k is not adjacent to
prev, the answer if we must take
(the point value of k) + max(avoid, using), and the answer if we must not take
At the end, the best answer may or may not use the largest value in
nums, so we return
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.
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
Time Complexity (Java): We performed a radix sort instead, so our complexity is where is the range of allowable values for
Space Complexity (Java): , the size of our
Analysis written by: @awice.