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

发表于 分类于 阅读次数： Waline： 本文字数： 1k 阅读时长 ≈ 3 分钟

考点

  • 线性DP

思路

一、问题重述

给定一个整数数组 nums，允许对 每个元素最多执行一次操作：将其加 1 或不变。 在此基础上，从数组中选取若干元素（不要求下标连续），使得 选出元素的最终数值能够构成一个连续整数序列，求该序列的最大长度。

二、问题建模

1. 排序的必要性

由于目标是构造 值连续 的序列，而不关心原数组下标，因此首先对数组排序。 排序后，问题转化为：按从小到大的顺序，依次决定每个元素是取原值 x，还是取修改后的值 x+1，以延长连续序列。

2. 状态定义

定义一维动态规划数组： \[ f[v] = \text{当前已经处理过的元素中，能构成的、以数值 } v \text{ 结尾的最长连续序列长度} \] 注意：

  • v 表示最终取值，而不是原数组中的值；
  • f[v] 的含义只依赖于已经处理过的元素，符合在线 DP 的特征。

三、状态转移方程设计

设当前处理到排序后的一个元素，其原始值为 \(x\)。

该元素有且仅有两种合法使用方式：

情况一：不修改该元素（取值为 \(x\)）

若该元素最终取值为 \(x\)，则它只能接在一个 以 \(x-1\) 结尾 的连续序列之后： \[ f[x] = \max\left( f[x],\ f[x-1] + 1 \right) \] 解释：

  • 如果之前不存在以 \(x-1\) 结尾的序列，则 \(f[x-1] = 0\)，相当于新开一个长度为 1 的序列；
  • 使用 max 是因为可能已有更优的以 \(x\) 结尾的方案。

情况二：修改该元素（取值为 \(x+1\)）

若该元素被加 1，最终取值为 \(x+1\)，则它只能接在一个 以 \(x\) 结尾 的连续序列之后： \[ f[x+1] = \max\left( f[x+1],\ f[x] + 1 \right) \] 解释：

  • 这是唯一能够把当前元素“向右延伸”连续性的方式；
  • 该转移必须使用 当前元素尚未作为 \(x\) 使用之前的 \(f[x]\)，否则会出现同一元素被重复计入的问题。

转移顺序的关键性

为了保证每个元素只被使用一次，在实现时必须遵循以下顺序：

  1. 先尝试将当前元素作为 \(x+1\) 使用（依赖旧的 \(f[x]\)）
  2. 再将当前元素作为 \(x\) 使用

这也是代码中先更新 f[x+1]、再更新 f[x] 的根本原因。

四、边界与初始化

  • 初始时，f[v] = 0 表示尚未构造任何序列；
  • 允许访问 f[0]，其值自然为 0，用于处理 x = 1 的情况；
  • 维护全局最大值 res，在每次状态更新后进行刷新。

五、时间与空间复杂度分析

  • 排序复杂度： \[ O(n \log n) \]

  • 动态规划转移： 每个元素仅进行常数次操作，复杂度为 \[ O(n) \]

  • 空间复杂度： 使用值域 DP 数组 \[ O(V) \] 其中 \(V \le 10^6\)。

六、AC代码

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:
    // 最大值域，题目中 nums[i] ≤ 1e6
    static const int maxn = 1e6 + 1;
    static const int inf = 1e6;

    int maxSelectedElements(vector<int>& nums) {
        // f[v]：以 v 结尾的最长连续序列长度
        int f[maxn] = {};
        int res = 1;

        // 排序，使得按值递增处理元素
        sort(nums.begin(), nums.end());

        for (int x : nums) {
            // 情况二：将当前元素 x 修改为 x+1
            // 必须先做这一步，确保使用的是“旧的 f[x]”
            if (x + 1 <= inf) {
                f[x + 1] = max(f[x + 1], f[x] + 1);
                res = max(res, f[x + 1]);
            }

            // 情况一：不修改当前元素，直接使用 x
            // 接在以 x-1 结尾的序列之后
            f[x] = max(f[x], f[x - 1] + 1);
            res = max(res, f[x]);
        }

        return res;
    }
};

七、总结

该问题的核心不在于复杂的数据结构，而在于 精确的状态定义与严格的转移约束：

  • 用 f[v] 表示“以值结尾”的最优解，避免与原数组下标耦合；
  • 明确区分“当前元素取 \(x\)”与“当前元素取 \(x+1\)”两种互斥选择；
  • 通过更新顺序保证每个元素只被使用一次。