740. Delete and Earn

You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:

• Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.

Return the maximum number of points you can earn by applying the above operation some number of times.

Example 1:

Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.

Example 2:

Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        points = [0]*(max(nums)+1)
        for num in nums:
            points[num] += num
        
        dp = [0]*len(points)
        for i in range(len(points)):
            dp[i] = max(points[i]+dp[i-2], dp[i-1])
        return dp[-1]

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        d = [0] *(max(nums)+1)
        for i in nums:
            d[i] += i
        prev,prever = 0,0 
        for i in d:
            cur = max(prev,prever+i)
            prever = prev
            prev = cur 
        return max(cur,prever)

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        '''
        [2 3 4]
        [2  3  6]
        
        [2,3, 8, 9, 11, 19]
         2 3  11 12  23 42 
        
        if last element isnt equal to i-1 -> add points
        if it is: max(dp[i-1], nums[i]+dp[i-2])
        '''
        
        h = {}
        for i in nums:
            if i not in h:
                h[i] = i
            else:
                h[i] = h[i]+ i
        
        nums = sorted(list(set(nums)))
        if len(nums) == 1: return h[nums[0]]
        if len(nums) == 2: 
            if nums[0]!=nums[1]-1:
                return (h[nums[1]]+h[nums[0]])
            else:
                return max(h[nums[1]],h[nums[0]])
        dp = [0] * len(nums)
        dp[0] = h[nums[0]]
        if nums[0] == nums[1] - 1:
            dp[1] = max(h[nums[1]],h[nums[0]])
        else:
            dp[1] = (h[nums[1]]+h[nums[0]])
        
        
        for i in range(2, len(nums)):
            if nums[i-1] == nums[i]-1:
                dp[i] = max(dp[i-1], dp[i-2]+h[nums[i]])
            else:
                dp[i] = h[nums[i]]+ dp[i-1]
        #print(nums,dp)
        return dp[-1]