Delete And Earn


  • 0

    Click here to see the full article post


  • 0
    S

    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.


  • 0
    M

    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.


  • 0
    R

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


  • 0

    @maverick247 I think that is discussed as a variant in the Java solution of Approach #1
    @rriskhh Thanks for the tip, I will think about how best to add this


  • 0
    Z
    This post is deleted!

  • 0
    I

    In Python solution, is "for k in sorted(count):" supposed to be "for k in sorted(nums):"?


Log in to reply
 

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