class Solution:
    def deleteAndEarn(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n=len(nums)
        if n==0:
            return 0
        if n==1:
            return nums[0]
        max_index=nums[0]
        for i in range(1,n,1):
            max_index=max(max_index,nums[i])
        num,dp=[0 for i in range(max_index+1)],[0 for i in range(max_index+1)]
        for item in nums:
            num[item]+=item
        dp[1]=num[1]
        for i in range(2,max_index+1,1):
            dp[i]=max(dp[i-1],dp[i-2]+num[i])
        return dp[max_index]

s=Solution()
nums=[2,1,2]
print(s.largestRectangleArea(nums))