Problem statement

https://leetcode.com/problems/delete-and-earn/

Solution

This problem is very similar to problem 0198 House Robber: here is again if we take number i, we can not take i-1 or i+1. Also note, that if we take some number i, than it is optimal to take all other occurrences of this number. So, let us use counter to get frequency of each number and then use the idea of House Robber: we always have two options: either we rob some house (dp1) or we not (dp2). The only difference here if we need to check if our current house is adjacent to previous:

  1. if it is, then: dp1 = max(dp1, dp2), dp2 = i*j + dp1, because for dp2 we gain i*j on the last step.
  2. if it is not, then again dp1 = max(dp1, dp2), but dp2 = i*j + max(dp1, dp2), because we do not have limit on adjacent element here.

Complexity

Time complexity is O(n log n), space is O(n).

Code

class Solution:
    def deleteAndEarn(self, nums):
        prev, dp1, dp2 = None, 0, 0
        for i, j in sorted(Counter(nums).items()):
            if i - 1 == prev:
                dp1, dp2 = max(dp1, dp2), i*j + dp1
            else:
                dp1, dp2 = max(dp1, dp2), i*j + max(dp1, dp2)
            prev = i
        return max(dp1, dp2)

Remark

Also, if we use bucket sort, instead of usual one, we will have time complexity O(n + N), where N = 10000 is range for our numbers, space complexity is O(N).