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] 不是连续的。

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

示例 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. 最长定差子序列 类似，将以每一个元素结尾的最长连续的长度统统存起来，即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:

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 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

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