Delete and Earn

• 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 [4] 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.

Constraints

• 1<= n <= 10 (to the power 5)

• 1 <= elements i <= 10 (to the power 5)

Sample Input : [3,4,2]
Output : 6

Explanation:
Given elements = [3,4,2], we maximize our score by performing the following steps:

1. Delete 4 to earn 4 points, which also deletes 4 - 1 = 3 and elements becomes [2].
2. 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 `2` is `4`. So we delete `2` first. We get only `4`. But if we delete `1` and `3` first. We get `6`.

Then the problem becomes pretty similar to https://leetcode.com/problems/house-robber/description/.
Say `A[i]` represents the sum of element `i`.

`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[0]` to `dp[MAX]`, which is `O(n)`. `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 `O(nlogn)`.

• def max_earn(elements):

if len(elements) == 0:
return 0

if len(elements) == 1:
return elements[0]

upper_limit = max(elements)+1
new_arr = [0]*upper_limit
for i in elements:
new_arr[i] += i

dp_arr = [0] * upper_limit
dp_arr[1] = max(new_arr[0], new_arr[1])
dp_arr[0] = new_arr[0]

for i in range(2, upper_limit):
dp_arr[i] = max(new_arr[i] + dp_arr[i - 2], dp_arr[i - 1])

return dp_arr[-1]

elements = [1,1,1,1]

print max_earn(elements)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.