最长递增子序列的变种：带限制的最长递增子序列（每个元素最多出现k次） 题目描述： 给定一个整数数组nums和一个整数k，要求找出最长递增子序列的长度，其中子序列中每个元素最多出现k次。注意：这里的子序列不要求连续，但必须保持原数组中的相对顺序。 举例说明： nums = [ 1, 2, 2, 3, 3, 3, 4 ], k = 2 最长递增子序列可以是[ 1, 2, 2, 3, 3, 4 ]，长度为6 解题思路： 这个问题是标准最长递增子序列(LIS)问题的变种，增加了每个元素出现次数不超过k次的限制。我们需要修改标准的动态规划解法来处理这个限制。 详细解题步骤： 状态定义： 定义dp[ i ]表示以第i个元素结尾的最长递增子序列的长度。 限制条件处理： 由于每个元素最多出现k次，我们需要记录在当前位置之前，当前元素已经出现了多少次。因此我们需要一个辅助数组count来记录。 状态转移方程： 对于每个位置i，我们需要： 遍历所有j < i，如果nums[ j] < nums[ i]，那么可以考虑将nums[ i]接在以nums[ j ]结尾的子序列后面 但是需要检查：如果nums[ j] == nums[ i]，那么我们需要确保在j到i的区间内，nums[ i ]出现的次数不超过k-1次（因为加上当前这个就是第k次） 更精确的状态转移： dp[ i] = max(1, max{dp[ j] + 1 | j < i, nums[ j] < nums[ i ], 且满足出现次数限制}) 出现次数限制的具体实现： 我们可以维护一个lastOccurrence数组来记录每个数值最近出现的k个位置，或者使用滑动窗口的思想。 算法优化： 直接的双重循环时间复杂度是O(n²)，但我们可以优化： 使用二分查找来加速 维护一个有序数据结构来快速找到满足条件的j 具体实现细节： 我们可以为每个不同的数值维护一个列表，记录该数值出现的位置，然后使用动态规划结合这些信息。 让我用一个完整的例子来演示： 示例：nums = [ 1, 2, 2, 3, 3, 3, 4 ], k = 2 步骤1：初始化 dp = [ 1, 1, 1, 1, 1, 1, 1 ] count = 记录每个数值出现次数的字典 步骤2：逐个处理每个元素： 位置0：数值1，dp[ 0 ] = 1 位置1：数值2，检查前面所有小于2的数：只有1，dp[ 1] = dp[ 0 ] + 1 = 2 位置2：数值2，检查前面： 数值1：dp[ 0 ] + 1 = 2 数值2：但数值2已经出现1次，还可以再出现1次，所以dp[ 2] = dp[ 1 ] + 1 = 3 位置3：数值3，检查前面小于3的数：1和2 从数值1：dp[ 0 ] + 1 = 2 从数值2：dp[ 1] + 1 = 3, dp[ 2 ] + 1 = 4 dp[ 3 ] = 4 以此类推... 最终得到最长递增子序列长度为6。 这个问题的关键在于正确处理每个数值的出现次数限制，确保在构建递增子序列时不超过k次的限制。