题目描述：
给你一个下标从 0 开始只包含 正 整数的数组 nums 。
一开始，你可以将数组中 任意数量 元素增加 至多 1 。
修改后，你可以从最终数组中选择 一个或者更多 元素，并确保这些元素升序排序后是 连续 的。比方说，[3, 4, 5] 是连续的，但是 [3, 4, 6] 和 [1, 1, 2, 3] 不是连续的。
请你返回 最多 可以选出的元素数目。
数据范围：
$1\le nums.len \le 10^5, 1\le nums[i] \le 10^6$
题解：
首先先排序，然后直接使用 $dp$ ，针对每一个数组选择修改与否。如果存在 $dp[x]$ ，则可以选择修改当前 $x$ ， $dp[x +1] = dp[x] + 1$ ，否则的话可以考虑接到 $dp[x - 1]$ 后面， $dp[x] = dp[x - 1] + 1$ 。如果使用 $count$ 判断的话需要注意初始状态。
也可以不使用 $count$ ，直接使用 $dp[x +1] = dp[x] + 1, dp[x] = dp[x - 1] + 1$ 。因为如果 $x$ 不存在， $mp[x] = 0$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
int maxSelectedElements(vector<int> &nums)
{
int n = nums.size();
sort(nums.begin(), nums.end());
unordered_map<int, int> mp;
for (int i = 0; i < n; ++i)
{
int x = nums[i];
if (mp.count(x))
mp[x + 1] = max(mp[x + 1], mp[x] + 1);
else mp[x] = mp[x + 1] = 1;
if (mp.count(x - 1))
mp[x] = max(mp[x], mp[x - 1] + 1);
else mp[x] = 1;
}
int ans = 0;
for (auto &[key, val] : mp)
{
ans = max(ans, val);
}
return ans;
}
};
|