740. Delete and Earn (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def deleteAndEarn(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # bucket sort + dp
        h, a, b = collections.Counter(nums), 0, 0
        for num in range(min(nums), max(nums) + 1):
            a, b = b, max(a + num * h[num], b)
        return b
        
        # sort + dp
        h = collections.Counter(nums)
        nums = sorted(set(nums)) + [0]
        result = i = 0
        while i < len(nums) - 1:
            a, b = 0, nums[i] * h[nums[i]]
            while nums[i + 1] - nums[i] == 1:
                a, b = b, max(a + nums[i + 1] * h[nums[i + 1]], b)
                i += 1
            else:
                result += b
                i += 1
        return result