Click here to see the full article post
This is really an elegant problem. As indicated by the first example, i.e., [2,3,4], the order of taking the numbers is also very crucial.
In this example, if one pick 3 as the first number, the other numbers,, i.e., 2 and 4 are to be deleted and 3 will be the result. However, if one pick 2 first, 3 is going to be deleted, and 4 can still be picked, and therefore, the optimum answer 6 is achieved.
This whole can be done in O(m) where m is the maximum number given in the input. Hashmap will store the count of how many times a number has occurred in given input and then using this hashmap we can compute the answer.
We can also do this in O(max - min) time using O(max - min) space complexity using a DP approach only, where max and min are the maximum and minimum number respectively in 'nums' (input array).
In Python solution, is "for k in sorted(count):" supposed to be "for k in sorted(nums):"?
My solution is that this problem can also be viewed as taking sums of even numbers or sums of odd numbers, plus ones that have no neighbors. ex: [1,3,5,6,7,8], 1 and 3 will go to both sum of even and odd. However, my program went wrong at 21st test case. Is there something wrong with my approach?
@liruan Yes, eg.
22222 3 4 55555
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.