线性动态规划：最长递增子序列的变种——带限制的最长递增子序列（每个元素最多出现k次）

字数 1887 2025-11-27 09:58:52

线性动态规划：最长递增子序列的变种——带限制的最长递增子序列（每个元素最多出现k次）

题目描述
给定一个整数数组 nums 和一个整数 k，要求找到最长的递增子序列（严格递增），且子序列中每个元素在原始数组中的出现次数不超过 k 次。注意，子序列不要求连续，但必须保持原数组中的相对顺序。

例如：
输入：nums = [1, 2, 3, 1, 2, 3, 1, 2, 3], k = 2
输出：最长递增子序列长度为 6（如 [1, 2, 3, 1, 2, 3]，每个数字出现不超过 2 次）。

解题过程

步骤 1：问题分析
本题是经典最长递增子序列（LIS）问题的变种，增加了“每个元素出现次数不超过 k 次”的限制。直接应用 LIS 的 O(n²) 或 O(n log n) 解法无法处理次数限制，需要扩展状态定义。

步骤 2：状态定义
设 dp[i][c] 表示以 nums[i] 结尾、且 nums[i] 在子序列中出现第 c 次（1 ≤ c ≤ k）时的最长递增子序列长度。

i 是数组索引（0 ≤ i < n）。
c 是当前元素在子序列中的出现次数（从 1 到 k）。

步骤 3：状态转移方程
对于每个 i 和 c，我们需要找到所有 j < i 满足：

nums[j] < nums[i]（递增条件）。
若 nums[j] = nums[i]，则 j 对应的次数 c_j 必须小于 c（因为当前是第 c 次出现 nums[i]，之前相同数字的出现次数应更少）。
若 nums[j] ≠ nums[i]，则 j 对应的次数可以是 1 到 k 的任意值。

状态转移方程：

dp[i][c] = 1 + max{ dp[j][c_j] }  对所有 j < i 满足上述条件

初始时，dp[i][1] = 1（每个元素单独作为子序列）。

步骤 4：优化转移
直接枚举 j 会带来 O(n²k) 的复杂度，可能过高。我们可以优化：

按值分组：对每个不同的数字，维护其在不同出现次数下的最大 dp 值。
使用树状数组或线段树：按数字大小排序，支持前缀最大值查询（对小于 nums[i] 的数字求最大 dp 值）。

具体做法：

对数组索引按 nums[i] 从小到大排序，相同数字按索引从小到大排序。
遍历排序后的列表，对于每个 (i, c)，查询所有小于 nums[i] 的数字的最大 dp 值（忽略相同数字的冲突情况）。
更新当前 dp[i][c] 后，将其值更新到数据结构中。

步骤 5：算法实现

初始化 dp[i][c] = 0，且 dp[i][1] = 1。
创建线段树（或树状数组），维护数字值域上的最大值。
按 nums[i] 排序后遍历：
- 对于每个 i，从 c = 1 到 k：
  - 查询值域 [min, nums[i]-1] 的最大 dp 值 max_val。
  - 若 max_val > 0，则 dp[i][c] = max_val + 1；否则 dp[i][c] = 1（仅当 c=1 时可能）。
- 更新线段树：将 dp[i][c] 更新到位置 nums[i]。
最终答案是所有 dp[i][c] 的最大值。

步骤 6：复杂度分析

时间复杂度：O(nk log n)，其中 n 是数组长度。
空间复杂度：O(nk)。

举例说明
以 nums = [1, 2, 3, 1, 2, 3, 1, 2, 3]，k = 2 为例：

排序后索引按值分组：1: [0, 3, 6], 2: [1, 4, 7], 3: [2, 5, 8]。
处理第一个 1（索引 0）：dp[0][1] = 1。
处理第一个 2（索引 1）：查询小于 2 的值（即 1）的最大 dp 值（1），则 dp[1][1] = 2。
处理第一个 3（索引 2）：查询小于 3 的值（1, 2）的最大 dp 值（2），则 dp[2][1] = 3。
处理第二个 1（索引 3）：查询小于 1 的值（无），但允许相同数字次数更少（此处无更少次数），所以 dp[3][2] = 1？不对！应查询小于 1 的值（无），但 c=2 时，需要找之前出现次数 <2 的相同数字（即第一个 1 的 c=1），所以 dp[3][2] = dp[0][1] + 1 = 2。
依此类推，最终最大值为 6。

通过以上步骤，我们可以高效求解带次数限制的最长递增子序列问题。

线性动态规划：最长递增子序列的变种——带限制的最长递增子序列（每个元素最多出现k次）题目描述给定一个整数数组 nums 和一个整数 k ，要求找到最长的递增子序列（严格递增），且子序列中每个元素在原始数组中的出现次数不超过 k 次。注意，子序列不要求连续，但必须保持原数组中的相对顺序。例如：输入： nums = [1, 2, 3, 1, 2, 3, 1, 2, 3] , k = 2 输出：最长递增子序列长度为 6（如 [1, 2, 3, 1, 2, 3] ，每个数字出现不超过 2 次）。解题过程步骤 1：问题分析本题是经典最长递增子序列（LIS）问题的变种，增加了“每个元素出现次数不超过 k 次”的限制。直接应用 LIS 的 O(n²) 或 O(n log n) 解法无法处理次数限制，需要扩展状态定义。步骤 2：状态定义设 dp[i][c] 表示以 nums[i] 结尾、且 nums[i] 在子序列中出现第 c 次（1 ≤ c ≤ k）时的最长递增子序列长度。 i 是数组索引（0 ≤ i < n）。 c 是当前元素在子序列中的出现次数（从 1 到 k）。步骤 3：状态转移方程对于每个 i 和 c ，我们需要找到所有 j < i 满足： nums[j] < nums[i] （递增条件）。若 nums[j] = nums[i] ，则 j 对应的次数 c_j 必须小于 c （因为当前是第 c 次出现 nums[i] ，之前相同数字的出现次数应更少）。若 nums[j] ≠ nums[i] ，则 j 对应的次数可以是 1 到 k 的任意值。状态转移方程：初始时， dp[i][1] = 1 （每个元素单独作为子序列）。步骤 4：优化转移直接枚举 j 会带来 O(n²k) 的复杂度，可能过高。我们可以优化：按值分组：对每个不同的数字，维护其在不同出现次数下的最大 dp 值。使用树状数组或线段树：按数字大小排序，支持前缀最大值查询（对小于 nums[i] 的数字求最大 dp 值）。具体做法：对数组索引按 nums[i] 从小到大排序，相同数字按索引从小到大排序。遍历排序后的列表，对于每个 (i, c) ，查询所有小于 nums[i] 的数字的最大 dp 值（忽略相同数字的冲突情况）。更新当前 dp[i][c] 后，将其值更新到数据结构中。步骤 5：算法实现初始化 dp[i][c] = 0 ，且 dp[i][1] = 1 。创建线段树（或树状数组），维护数字值域上的最大值。按 nums[i] 排序后遍历：对于每个 i ，从 c = 1 到 k ：查询值域 [min, nums[i]-1] 的最大 dp 值 max_val 。若 max_val > 0 ，则 dp[i][c] = max_val + 1 ；否则 dp[i][c] = 1 （仅当 c=1 时可能）。更新线段树：将 dp[i][c] 更新到位置 nums[i] 。最终答案是所有 dp[i][c] 的最大值。步骤 6：复杂度分析时间复杂度：O(nk log n)，其中 n 是数组长度。空间复杂度：O(nk)。举例说明以 nums = [1, 2, 3, 1, 2, 3, 1, 2, 3] ， k = 2 为例：排序后索引按值分组： 1: [0, 3, 6] , 2: [1, 4, 7] , 3: [2, 5, 8] 。处理第一个 1（索引 0）： dp[0][1] = 1 。处理第一个 2（索引 1）：查询小于 2 的值（即 1）的最大 dp 值（1），则 dp[1][1] = 2 。处理第一个 3（索引 2）：查询小于 3 的值（1, 2）的最大 dp 值（2），则 dp[2][1] = 3 。处理第二个 1（索引 3）：查询小于 1 的值（无），但允许相同数字次数更少（此处无更少次数），所以 dp[3][2] = 1 ？不对！应查询小于 1 的值（无），但 c=2 时，需要找之前出现次数 <2 的相同数字（即第一个 1 的 c=1），所以 dp[3][2] = dp[0][1] + 1 = 2 。依此类推，最终最大值为 6。通过以上步骤，我们可以高效求解带次数限制的最长递增子序列问题。