# 3041. 修改数组后最大化数组中的连续元素数目
### 题目地址(3041. 修改数组后最大化数组中的连续元素数目 - 力扣（LeetCode）)
### 题目描述
给你一个下标从 **0** 开始只包含 **正** 整数的数组 `nums` 。
一开始，你可以将数组中 **任意数量** 元素增加 **至多** `1` 。
修改后，你可以从最终数组中选择 **一个或者更多** 元素，并确保这些元素升序排序后是 **连续** 的。比方说，`[3, 4, 5]` 是连续的，但是 `[3, 4, 6]` 和 `[1, 1, 2, 3]` 不是连续的。
请你返回 **最多** 可以选出的元素数目。
**示例 1：**
输入：nums = [2,1,5,1,1]
输出：3
解释：我们将下标 0 和 3 处的元素增加 1 ，得到结果数组 nums = [3,1,5,2,1] 。
我们选择元素 [3,1,5,2,1] 并将它们排序得到 [1,2,3] ，是连续元素。
最多可以得到 3 个连续元素。
**示例 2：**
```
输入：nums = [1,4,7,10]
输出：1
解释：我们可以选择的最多元素数目是 1 。
```
**提示：**
* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 106`
### 前置知识
* 动态规划
### 公司
* 暂无
### 思路
和 [1218. 最长定差子序列](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1218.longest-arithmetic-subsequence-of-given-difference) 类似，将以每一个元素结尾的最长连续的长度统统存起来，即dp\[num] = maxLen 这样我们遍历到一个新的元素的时候，就去之前的存储中去找dp\[num - 1], 如果找到了，就更新当前的dp\[num] = dp\[num - 1] + 1, 否则就是不进行操作（还是默认值 1）。
由于要求排序后连续（这和 1218 是不一样的），因此对顺序没有要求。我们可以先排序，方便后续操作。
另外特别需要注意的是由于重排了，当前元素可能作为最后一个，也可能作为最后一个的前一个，这样才完备。因为要额外更新 dp\[num+1]， 即 dp\[num+1] = memo\[num]+1
整体上算法的瓶颈在于排序，时间复杂度大概是 $O(nlogn)$
### 关键点
* 将以每一个元素结尾的最长连续子序列的长度统统存起来
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def maxSelectedElements(self, arr: List[int]) -> int:
memo = collections.defaultdict(int)
arr.sort()
def dp(pos):
if pos == len(arr): return 0
memo[arr[pos]+1] = memo[arr[pos]]+1 # 由于可以重排，因此这一句要写
memo[arr[pos]] = memo[arr[pos]-1]+1
dp(pos+1)
dp(0)
return max(memo.values())
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(nlogn)$
* 空间复杂度：$O(n)$
### 相关题目
* [1218. 最长定差子序列](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1218.longest-arithmetic-subsequence-of-given-difference)
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
