> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/3041.maximize-consecutive-elements-in-an-array-after-modification.md).

# 3041. 修改数组后最大化数组中的连续元素数目

### 题目地址(3041. 修改数组后最大化数组中的连续元素数目 - 力扣（LeetCode）)

<https://leetcode.cn/problems/maximize-consecutive-elements-in-an-array-after-modification/>

### 题目描述

给你一个下标从 **0** 开始只包含 **正** 整数的数组 `nums` 。

一开始，你可以将数组中 **任意数量** 元素增加 **至多** `1` 。

修改后，你可以从最终数组中选择 **一个或者更多** 元素，并确保这些元素升序排序后是 **连续** 的。比方说，`[3, 4, 5]` 是连续的，但是 `[3, 4, 6]` 和 `[1, 1, 2, 3]` 不是连续的。

请你返回 **最多** 可以选出的元素数目。

&#x20;

**示例 1：**

<pre><code>输入：nums = [2,1,5,1,1]
输出：3
解释：我们将下标 0 和 3 处的元素增加 1 ，得到结果数组 nums = [3,1,5,2,1] 。
<strong>我们选择元素 [3,1,5,2,1] 并将它们排序得到 [1,2,3] ，是连续元素。
</strong>最多可以得到 3 个连续元素。
</code></pre>

**示例 2：**

```
输入：nums = [1,4,7,10]
输出：1
解释：我们可以选择的最多元素数目是 1 。
```

&#x20;

**提示：**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 106`

### 前置知识

* 动态规划

### 公司

* 暂无

### 思路

和 [1218. 最长定差子序列](/leetcode-solution/medium/1218.longest-arithmetic-subsequence-of-given-difference.md) 类似，将以每一个元素结尾的最长连续的长度统统存起来，即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. 最长定差子序列](/leetcode-solution/medium/1218.longest-arithmetic-subsequence-of-given-difference.md)

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/h9nm77.jpg)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/3041.maximize-consecutive-elements-in-an-array-after-modification.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.