Delete And Earn

  • 0

    Click here to see the full article post

  • 0

    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

    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

    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
    This post is deleted!

  • 0

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

  • 0

    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?

  • 0

    @liruan Yes, eg.
    22222 3 4 55555

Log in to reply

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