题解 | 删除相邻数字的最大分数

import sys


# 分析： 当从小到达处理数字的时候， 计算当数组包含 0～i，考虑到数字i的时候，其只和i-1和i-2有关
# 即，当数组只包含0~i个数的时候的最高分dp[i],其最高分要么是我选择了第i个数，要么没选
# 如果选择了第i个数 dp[i] = dp[i-2] + i * count[i], 因为选了i，所以i-1不能选，和i-2有关
# 如果没选第i个数，dp[i] = dp[i-1], 并且因为选择数有得分，即dp[i]肯定>dp[i-2]，所以保证最优子结构

n = int(input())

nums = list(map(int,input().strip().split()))

max_num = max(nums)
counter = [0] * (max_num+1)
for num in nums:
    counter[num] += 1

dp = [0] * (max_num+1)

for i in range(1,max_num+1):
    dp[i] = max(dp[i-2]+i*counter[i],dp[i-1])

print(dp[max_num])