Delete and Earn


  • 0
    S

    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.


  • 1
    I

    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).


Log in to reply
 

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