740. Delete and Earn

class Solution:
    def deleteAndEarn(self, A: List[int]) -> int:
        """ tc O(N) sc O(N) N: max(A)
        dp[i] the most score can get for sorted number array [0,i]  (both inclusive )
        """
        n = 10001
        if n == 1: # optimization 
            return A[0]
        x_sum = [0]*n
        for a in A:
            x_sum[a] += a 
        dp = [0]*n
        dp[0] = x_sum[0]
        dp[1] = x_sum[1]
        for i in range(2,1001):
            dp[i] = max(dp[i-1], dp[i-2]+x_sum[i])
        return dp[-1]

class Solution:
    def deleteAndEarn(self, A: List[int]) -> int:
        """ tc O(N) sc O(N) N: max(A)
        dp[i] the most score can get for sorted number array [0,i]  (both inclusive )
        note here x_sum has to be sorted if not using bucket sort.  
        """
        n = 10001
        if n == 1: # optimization 
            return A[0]
        x_sum = [0]*n
        for a in A:
            x_sum[a] += a 
        dp1 = dp2 = 0
        for i in range(10001):
            # for next step current dp is dp1, current dp1 is dp2 
            dp = max(dp1, dp2 +x_sum[i]) # dp[i]
            dp2 = dp1 
            dp1 = dp
        return dp