题目描述
给定一个整数数组 nums
,你可以对它进行一些操作。
每次操作中,选择任意一个 nums[i]
,删除它并获得 nums[i]
的点数。之后,你必须删除每个等于 nums[i] - 1
或 nums[i] + 1
的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
样例
输入:nums = [3, 4, 2]
输出:6
解释:
删除 4 来获得 4 个点数,因此 3 也被删除。
之后,删除 2 来获得 2 个点数。总共获得 6 个点数。
输入:nums = [2, 2, 3, 3, 3, 4]
输出:9
解释:
删除 3 来获得 3 个点数,接着要删除两个 2 和 4 。
之后,再次删除 3 获得 3 个点数,再次删除 3 获得 3 个点数。
总共获得 9 个点数。
限制
nums
的长度最大为20000
。- 每个整数
nums[i]
的大小都在[1, 10000]
范围内。
算法
(动态规划) $O(n + m)$
- 首先求出每种数字出现的次数,并将其存在
[1, 10000]
的tot
数组里,我们对这个数组进行动态规划,这个动态规划和有冷冻期的股票买卖一样。 - 设 $f(i, 0)$ 表示遍历了前 $i$ 种数字,且不取当前数字时的最大值。 $f(i, 1)$ 表示遍历了前 $i$ 种数字,取当前数字时的最大值。
- 初始时,$f(0, 0) = 0$,$f(0, 1) = -\infty$。
- 转移时,如果不取当前数字,则直接转移 $f(i, 0) = \max(f(i - 1, 0), f(i - 1, 1))$。如果取当前数字,则 $f(i, 1) = f(i - 1, 0) + tot(i) \cdot i$。
- 最终答案为 $\max(f(m, 0), f(m, 1))$。
时间复杂度
- 遍历初始数字一次,然后线性动态规划,故时间复杂度为 $O(n + m)$,其中 $n$ 为原始数组长度,$m$ 为最大的数字。
空间复杂度
- 需要额外的空间记录每个数字出现了多少次以及状态,故空间复杂度为 $O(m)$。
C++ 代码
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
const int N = 10010;
int m = 0;
vector<int> tot(N, 0);
for (int x : nums) {
tot[x]++;
m = max(m, x);
}
vector<vector<int>> f(m + 1, vector<int>(2));
f[0][0] = 0;
f[0][1] = INT_MIN;
for (int i = 1; i <= m; i++) {
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + tot[i] * i;
}
return max(f[m][0], f[m][1]);
}
};
这里为什么选择直接枚举从0到m的所有数字呢, 并不是所有数字都出现过
也可以不遍历所有数字,但实现起来稍微麻烦些
这波代码比 y 的美很多,并且因为引入了 m 使得代码逻辑更加清晰
精髓都是一样的,不同的人有不同的代码习惯,集思广益
第四点求最大值的时候一定是f(i−2,1)+tot[i]∗i 而不用先确定 f(i-2, 0) 和 f(i - 2, 1) 两者的最大值吗
f(i-2,0)合法吗?
遍历里前 i - 2 种数字,且不取当前数字的最大值,这个状态不可以吗
时间太久远题目之前看错了
这里修正了一下,其实 $f(i,1)$ 直接取 $f(i−1,0)+tot(i) \cdot i$ 就行了,不需要再关注 $f(i−2)$。
看了前几行 就茅塞顿开。谢谢