Given an array of n integers named elements, we can perform several steps on the array. In each step, we choose an elementsi from the array and delete it to earn elements i points; However, deleting elements i also deletes any integers equal to elements i + 1 and elements i - 1 from elements. For exampls, if elements = [1,2,3,4], deleting 2 results in elements becoming  and earns us 2 points.
Compute the maxPoints function that has one parameter; an array of n integers named elements. The function must return a long integer denoting the maximum number of points we can earn by performing steps.
1<= n <= 10 (to the power 5)
1 <= elements i <= 10 (to the power 5)
Sample Input : [3,4,2]
Output : 6
Given elements = [3,4,2], we maximize our score by performing the following steps:
- Delete 4 to earn 4 points, which also deletes 4 - 1 = 3 and elements becomes .
- Delete 2 to earn 2 points and elements become 
There are no more elements to delete, so we can't perform any more steps. The function returns the total number of points which is 4 + 2 = 6.
First I come up with the idea that each time we delete the maximum value. But it obviously doesn't work in this case:
1 1 1 2.
So I think about storing how many times a certain value occurs. Then each time we delete the element whose sum is the largest. But again it doesn't work in this case:
1 1 1 2 2 3. The sum of
4. So we delete
2 first. We get only
4. But if we delete
3 first. We get
Then the problem becomes pretty similar to https://leetcode.com/problems/house-robber/description/.
A[i] represents the sum of element
dp[i] = max(dp[i - 1], dp[i - 2] + A[i])
Suppose the maximum of the elements is
MAX. Then we can simply go from
dp[MAX], which is
dp[MAX] is our answer. Since
MAX <= 10^5, we can do this. Otherwise we need to use
unordered_map then sort the
unordered_map. Or directly use
map(I'm talking about C++). The time complexity of either of them will become
if len(elements) == 0:
if len(elements) == 1:
upper_limit = max(elements)+1
new_arr = *upper_limit
for i in elements:
new_arr[i] += i
dp_arr =  * upper_limit
dp_arr = max(new_arr, new_arr)
dp_arr = new_arr
for i in range(2, upper_limit):
dp_arr[i] = max(new_arr[i] + dp_arr[i - 2], dp_arr[i - 1])
elements = [1,1,1,1]