[LeetCode]Delete and Earn

标准的DP类型的题目。我们先从小到大sort input array nums，并且把相同的group在一起得到count数组。比如nums = [4,3,2,1,2,4]就变为count = [(1, 1),(2, 2),(3, 1),(4,2)]，括号内第二个数字代表相同的元素有多少个。我们创建dp数组：

• 定义dp[i][0]为只考虑count的0-i的元素并且不选择位于i的元素情况下的最大值
• 定义dp[i][1]为只考虑count的0-i的元素并且选择位于i的元素情况下的最大值

我们有递推公式：

• 如果count[i].first == count[i-1].first + 1
• dp[i][0] = max(dp[i-1][0], dp[i - 1][1])
• dp[i][1] = max(dp[i - 1][1], dp[i-1][0] + count[i].first * count[i].second)
• else
• dp[i][0] = max(dp[i-1][0], dp[i - 1][1])
• dp[i][1] = max(max(dp[i-1][0], dp[i - 1][1]) + count[i].first * count[i].second)

时间复杂度取决于sort，O(n * log n)，空间复杂度O(n)。这里我们用BST记录count，之后顺序遍历即可，时间复杂度是一样的。代码如下：