最长递增子序列的变种：带限制的最长递增子序列（每个元素最多出现k次） 题目描述 给定一个整数数组nums和一个整数k，找到最长递增子序列的长度，要求这个子序列中每个元素最多出现k次。注意：子序列不要求连续，但必须保持原数组中的相对顺序。 例如： nums = [ 1, 2, 2, 3, 3, 3, 4 ], k = 2 最长递增子序列为[ 1, 2, 2, 3, 3, 4 ]，长度为6（其中2出现2次，3出现2次，都满足最多出现k=2次的限制） 解题思路 这个问题是经典最长递增子序列（LIS）问题的变种，增加了每个元素出现次数不超过k次的限制。我们需要在动态规划状态中记录元素出现的次数信息。 详细解题步骤 步骤1：定义状态 定义dp[ i][ c ]表示以第i个元素结尾，且该元素在子序列中出现次数为c时的最长递增子序列长度。 由于数组可能很大，我们需要优化状态表示。实际上，我们可以按元素值分组，对每个不同的数值维护其出现位置。 步骤2：状态转移 对于每个位置i，考虑所有可能的出现次数c（1 ≤ c ≤ k）： 如果c = 1，表示这是该元素第一次出现在子序列中 dp[ i][ 1] = 1 + max{dp[ j][ c']} 对于所有j < i且nums[ j] < nums[ i ]，c' ≤ k 如果c > 1，表示该元素已经出现过c-1次 我们需要找到前一个相同元素的位置p，且该位置的出现次数为c-1 dp[ i][ c] = dp[ p][ c-1 ] + 1（如果存在这样的p） 步骤3：优化实现 直接实现上述状态转移会超时，我们需要优化： 对每个不同的数值，记录其所有出现位置 使用树状数组或线段树来快速查询前缀最大值 步骤4：具体算法 预处理：记录每个数值的所有出现位置 初始化dp数组为0 按顺序遍历数组： 对于每个位置i，考虑所有出现次数c（1到k） 如果c=1：查询所有小于nums[ i ]的数值对应的最大dp值 如果c>1：找到nums[ i ]的前一个出现位置（第c-1次出现） 更新dp[ i][ c ] 更新数据结构 步骤5：最终答案 答案是所有dp[ i][ c ]中的最大值 举例说明 以nums = [ 1, 2, 2, 3, 3, 3, 4 ], k = 2为例： 处理过程： 位置0（值1）：dp[ 0][ 1 ] = 1 位置1（值2）：dp[ 1][ 1] = max(0, dp[ 0][ 1 ]) + 1 = 2 位置2（值2）：dp[ 2][ 1] = max(0, dp[ 0][ 1 ]) + 1 = 2 dp[ 2][ 2] = dp[ 1][ 1 ] + 1 = 3 位置3（值3）：dp[ 3][ 1] = max(dp[ 0..2 ]) + 1 = 4 位置4（值3）：dp[ 4][ 1] = max(dp[ 0..2 ]) + 1 = 4 dp[ 4][ 2] = dp[ 3][ 1 ] + 1 = 5 位置5（值3）：dp[ 5][ 2] = dp[ 4][ 1 ] + 1 = 5（不能有第3次出现，因为k=2） 位置6（值4）：dp[ 6][ 1] = max(dp[ 0..5 ]) + 1 = 6 最终答案为6，对应子序列[ 1, 2, 2, 3, 3, 4 ]。 这个算法的时间复杂度是O(nk logM)，其中M是数值范围，可以通过离散化优化到O(nk logn)。