class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        nums.sort()

        # Create an array starting with 0 and ending with 0, so that each run of
        # adjacent numbers are separated by 0s and repeated numbers are summed
        # together
        values = [0]
        cur_num = None
        for n in nums:
            if n != cur_num:
                values.append(0)
                if cur_num is not None and cur_num + 1 != n:
                    values.append(0)
                cur_num = n
            values[-1] += n
        values.append(0)

        N = len(values)

        # DP[i] = maximum value for values[:i + 1], where if you pick value[j],
        # you're not allowed to pick value[j - 1] or value[j + 1]
        dp = [0] * (N - 1)
        for i in range(1, N - 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + values[i])

        return dp[-1]