最长递增子序列的变种：每个元素最多使用k次的最长非递减子序列

字数 6513 2025-12-07 04:02:17

最长递增子序列的变种：每个元素最多使用k次的最长非递减子序列

题目描述

给定一个整数数组 nums 和一个正整数 k，你需要找出最长的非递减子序列（子序列中的每个元素都大于等于其前一个元素），并且数组中的每个元素在原数组中最多可以被使用 k 次。注意，这里的“使用”是指在构造子序列时，可以从原数组的对应位置“选取”这个元素，但原数组中每个位置的元素可以被选取的次数上限是它在整个数组中出现的次数乘以 k 吗？不，题目更常见的描述是：我们有一个序列，但每个元素可以被无限次使用吗？也不是。让我们澄清一下。

更准确的描述是：我们有一个可重复的序列 nums，你可以从nums中多次选择同一个值（注意，是同一个数值，而不是同一个位置），但是在构造出的子序列中，任何数值 x 最多连续出现 k 次。换句话说，子序列中不能有超过 k 个连续的相同值。但这里“最多使用k次”通常指整个子序列中，某个特定值最多出现k次，而不是连续。然而，在标准的“每个元素最多使用k次”的LIS变种中，通常是指：原数组提供了每个元素，但你可以从原数组中重复选取同一个元素（想象你有无穷多个相同的数字可用），但每个值在整个子序列中最多出现 `k`` 次。但这样问题就退化到对值的计数了，不是动态规划。另一种常见变种是：你有一个序列，每个位置i的元素可以被使用最多k次（但位置是唯一的，这说不通）。

我们设定一个经典变种：给你一个数组 nums，你可以从数组中删除一些元素（也可以不删除），形成一个新序列，但要求新序列是非递减的，并且原数组中每个位置的元素不能被重复使用（每个位置最多用一次），但是数组里可能有重复值。现在额外增加一个限制：在生成的子序列中，任何值最多可以出现 k 次。注意，这是对子序列中值出现频率的限制，而不是对原数组元素使用次数的限制（原数组每个位置只能用一次）。举个例子：

nums = [1, 2, 2, 3, 3, 3, 4], k = 2

原数组有多个重复值。最长非递减子序列可以是 [1, 2, 2, 3, 3, 4]，其中2出现了2次，3出现了2次，没有超过k=2。但你不能取三个3，因为值3最多出现2次。所以最终长度是6。

你的任务是计算满足以下条件的最长子序列的长度：

子序列是非递减的（即 a[i] <= a[i+1]）。
在子序列中，任何值 v 出现的次数不超过 k。

注意：子序列不要求连续，可以从原数组删除任意元素得到，但顺序需保持原顺序。

解题思路

这是一个带限制的最长非递减子序列（LNDS）问题。如果没有k的限制，就是经典的LIS（非递减版），可以用O(n²)动态规划或O(n log n)的贪心+二分查找。但有了“每个值最多出现k次”的限制，我们需要在状态中记录当前子序列末尾的值以及该值已连续（或在整体中）出现了多少次。

关键观察：由于子序列要求非递减，当我们往子序列中添加一个数字x时，如果x大于当前末尾值，那么添加后x的出现次数重置为1（因为这是一个新的值开始）。如果x等于当前末尾值，那么x的出现次数加1，但不能超过k。所以我们需要在状态中记录：

当前考虑到了原数组的哪个位置 i。
当前子序列的最后一个值 lastVal。
当前子序列中末尾这个值 lastVal 已经连续出现了多少次 cnt（注意，因为是非递减，所以末尾连续相同值就是整个子序列中这个值出现的总次数，因为相同的值只会连续出现，不会在中间插入其他值后再出现相同的值，否则就不是非递减了。但如果我们允许子序列是 [1,2,1] 吗？不允许，因为1再次出现时，前面的2比1大，序列不是非递减。所以，相同值在非递减子序列中必然是连续的一段。因此，我们只需要记录末尾值的连续出现次数，也就等于这个值在子序列中出现的总次数）。

但是，lastVal 的可能取值很多（如果数字范围大）。我们需要状态压缩。一个常见技巧是：我们并不需要精确知道 lastVal 是多少，只需要知道它是原数组中的某个值，而且当我们决定在子序列末尾添加 nums[i] 时，我们需要判断 nums[i] 与 lastVal 的大小关系。因此，我们可以将状态设计为：dp[i][c] 表示以原数组第 i 个元素结尾的子序列，并且这个子序列末尾的值（即 nums[i]）在该子序列中连续出现了 c 次（显然 1 <= c <= k）时，所能得到的最长子序列长度。

状态转移：

当我们考虑以 i 结尾的子序列，且末尾值出现了 c 次，那么这个子序列的倒数第二个元素可能是某个 j < i 且 nums[j] <= nums[i]。但还需要满足：如果 nums[j] < nums[i]，那么添加 nums[i] 后，nums[i] 是新的值，所以 c 必须是1（即 nums[i] 第一次出现）。如果 nums[j] == nums[i]，那么添加 nums[i] 后，末尾相同值的出现次数从 c-1 增加到了 c，所以前一个状态是以 j 结尾且末尾值出现次数为 c-1 的子序列。

因此，转移方程可以写为：

如果 c == 1：dp[i][1] = 1 + max{ dp[j][*] } 对所有 j < i 且 nums[j] <= nums[i]，这里 * 表示从1到k的任何次数，但注意必须满足 nums[j] < nums[i] 或者 nums[j] == nums[i] 但此时 c 必须是1，所以实际上当 c=1 时，nums[i] 是新值，所以前一个结尾的值必须小于 nums[i]（不能等于，因为等于的话就会使相同值次数>1）。所以条件应该是 nums[j] < nums[i]。另外，也可以没有前一个元素，即单独以 i 开头，长度为1。
如果 c > 1：那么前一个元素必须等于 nums[i]，且前一个状态中末尾值的出现次数是 c-1。即 dp[i][c] = 1 + dp[j][c-1] 对某个 j < i 且 nums[j] == nums[i]。同样，也可以从自己开始，但 c>1 时自己开始不可能，因为单个元素c=1。

然而，这个动态规划复杂度是 O(n² * k)，在n较大时会超时。我们需要优化。

优化思路：
注意到，我们需要快速查询：

对于 c=1：所有 j < i 且 nums[j] < nums[i] 的 max(dp[j][*])。
对于 c>1：所有 j < i 且 nums[j] == nums[i] 的 dp[j][c-1]。

我们可以用数据结构来维护：

对每个不同的值 v，维护一个数组 best[v][c] 表示以值 v 结尾，且末尾值出现次数为 c 时的最大子序列长度。但我们需要按原数组顺序更新，所以当处理到 i 时，我们需要查询所有值小于 nums[i] 的 max(best[小于v][*])，以及值等于 nums[i] 的 best[nums[i]][c-1]。

因为值的范围可能很大，我们可以对值进行离散化（排序+去重）。然后用树状数组（Fenwick Tree）或线段树来维护前缀最大值（对离散化后的值）。具体地，我们维护 k 个树状数组 BIT[c]，其中 BIT[c] 存储：以某个值 v 结尾，且末尾值出现次数为 c 时的最大长度。这样，当计算 dp[i][c] 时：

如果 c=1：我们需要查询所有值严格小于 nums[i] 的各个次数下的最大长度，即 max_{v < nums[i]} max_{t=1..k} BIT[t].query(v-1)。我们可以额外维护一个“全局”树状数组 BIT_all，它存储每个值 v 在所有次数下的最大长度，即 max_{t=1..k} best[v][t]。那么 dp[i][1] = 1 + BIT_all.query(rank(nums[i])-1)，其中 rank 是离散化后的秩（1-based）。如果查询为空，则 dp[i][1]=1。
如果 c>1：我们需要查询值等于 nums[i] 且次数为 c-1 的最大长度，即 dp[i][c] = 1 + best[nums[i]][c-1]，其中 best[nums[i]][c-1] 是之前计算过的、以值 nums[i] 结尾且次数为 c-1 的最大长度。注意，可能有多个位置 j 都以值 nums[i] 结尾，我们取最大的那个长度作为 best[nums[i]][c-1]。

在计算完 dp[i][c] 后，我们需要更新 best[nums[i]][c] 为 max(best[nums[i]][c], dp[i][c])，并相应更新树状数组 BIT_all 在值 nums[i] 处的值为 max(BIT_all.query(rank(nums[i])), dp[i][c])（实际上 BIT_all 存储的是这个值所有次数下的最大值，所以我们更新时需要用新的最大值去更新，但树状数组通常支持单点更新为更大值，需要先查询当前值，如果新值更大才更新）。

算法步骤：

离散化：将 nums 中所有值去重排序，得到每个值对应的秩 id，从1到m。
初始化：创建两个数组（或字典） best[m+1][k+1]，全部置0。创建树状数组 BIT_all 大小为 m+1，初始为0。
按顺序遍历原数组 nums 的每个元素 x，设其离散化秩为 idx。
- 先计算 c=1 的情况：len1 = 1 + BIT_all.query(idx-1)。如果查询为0，则 len1=1。
- 然后计算 c=2..k 的情况：lenc = 1 + best[idx][c-1]。注意，如果 best[idx][c-1]==0，说明之前没有以值x结尾且次数为c-1的子序列，那么 lenc 应该为0（无效）。实际上，lenc 的有效性要求 best[idx][c-1] > 0。
- 对于每个 c=1..k，如果计算出的长度 dp_c 大于0，则更新 best[idx][c] = max(best[idx][c], dp_c)，并更新树状数组：查询当前 BIT_all 在 idx 位置的值 old = BIT_all.point_query(idx)，如果 dp_c > old，则执行 BIT_all.update(idx, dp_c)。
最终答案是所有 best[i][c] 中的最大值，以及 BIT_all.query(m) 的最大值（其实 BIT_all 的全局最大值就是答案）。

复杂度：遍历数组 n 次，内层循环 k 次，每次树状数组操作 O(log m)，总复杂度 O(nk log m)，其中 m 是不同值的个数。如果 k 较小，可以接受。

边界情况：

如果 k=1，那么就是标准的严格递增子序列（因为相同值不能出现超过1次，但题目要求非递减，所以实际上不允许相等，等同于严格递增）。但注意，如果原题要求非递减，k=1 时意味着不允许重复值，所以等价于严格递增。
如果 k >= n，那么相当于没有限制，就是标准的非递减子序列（LNDS），可以用 O(n log n) 的贪心算法，但这里我们的算法也能工作，只是复杂度稍高。

例子：nums = [1,2,2,3,3,3,4], k=2

离散化值：{1:1, 2:2, 3:3, 4:4}
初始化 best[5][3]=0, BIT_all[5]=0.

i=0, x=1, idx=1
c=1: BIT_all.query(0)=0 -> len1=1
c=2: best[1][1]=0 -> len2=0 (无效)
更新 best[1][1]=1, BIT_all.update(1,1)

i=1, x=2, idx=2
c=1: BIT_all.query(1)=1 -> len1=2
c=2: best[2][1]=0 -> len2=0
更新 best[2][1]=2, BIT_all.update(2,2)

i=2, x=2, idx=2
c=1: BIT_all.query(1)=1 -> len1=2
c=2: best[2][1]=2 -> len2=3
更新 best[2][1]=max(2,2)=2, best[2][2]=3, BIT_all.update(2,3) (因为3>2)

i=3, x=3, idx=3
c=1: BIT_all.query(2)=3 -> len1=4
c=2: best[3][1]=0 -> len2=0
更新 best[3][1]=4, BIT_all.update(3,4)

i=4, x=3, idx=3
c=1: BIT_all.query(2)=3 -> len1=4
c=2: best[3][1]=4 -> len2=5
更新 best[3][1]=4, best[3][2]=5, BIT_all.update(3,5)

i=5, x=3, idx=3
c=1: BIT_all.query(2)=3 -> len1=4
c=2: best[3][2]=5 -> len2=6
但注意，c=2 时，我们要求末尾值出现次数为2，前一个状态末尾值出现次数为1，且值相等。best[3][2]=5 表示之前有长度为5且以3结尾出现2次的子序列。现在再加一个3，那么末尾值出现次数变为3，但 k=2 不允许出现3次，所以 c=3 不允许。所以这里 c=2 已经达到上限，不能再增加。实际上，当 c>k 时我们不考虑。所以对于 i=5, x=3, 我们只能计算 c=1,2。c=2 时，len2=1+best[3][1]=1+4=5，与之前一样。c=1 时 len1=4。所以没有更长的。但注意，我们之前已经有 best[3][2]=5，现在又得到5，不变。
更新：best[3][1] 保持4，best[3][2]保持5，BIT_all不变。

i=6, x=4, idx=4
c=1: BIT_all.query(3)=5 -> len1=6
c=2: best[4][1]=0 -> len2=0
更新 best[4][1]=6, BIT_all.update(4,6)

最终最大值为6，对应子序列 [1,2,2,3,3,4] 或 [1,2,2,3,3,4] 等。

总结：这个算法通过树状数组优化了小于当前值的查询，并通过 best 数组记录了相同值的状态，实现了 O(nk log m) 的时间复杂度。如果 k 较小，这是一个高效的解法。注意，如果 k 很大（比如 k>=n），我们可以退化成普通的 LIS 贪心算法，但这里不展开。

扩展：这个问题的变种可以改成“每个值最多出现 k 次，但不要求连续”，但在非递减子序列中，相同值必然连续，所以没有区别。如果原题是严格递增，那么相同值不允许出现，k 限制就没有意义（除非 k>=1）。所以本题设定为非递减是合理的。

希望这个讲解能让你理解这个线性动态规划问题的解法。

最长递增子序列的变种：每个元素最多使用k次的最长非递减子序列题目描述给定一个整数数组 nums 和一个正整数 k ，你需要找出最长的非递减子序列（子序列中的每个元素都大于等于其前一个元素），并且数组中的每个元素在原数组中最多可以被使用 k 次。注意，这里的“使用”是指在构造子序列时，可以从原数组的对应位置“选取”这个元素，但原数组中每个位置的元素可以被选取的次数上限是它在整个数组中出现的次数乘以 k 吗？不，题目更常见的描述是：我们有一个序列，但每个元素可以被无限次使用吗？也不是。让我们澄清一下。更准确的描述是：我们有一个可重复的序列 nums ，你可以从 nums 中多次选择同一个值（注意，是同一个数值，而不是同一个位置），但是在构造出的子序列中，任何数值 x 最多连续出现 k 次。换句话说，子序列中不能有超过 k 个连续的相同值。但这里“最多使用k次”通常指整个子序列中，某个特定值最多出现k次，而不是连续。然而，在标准的“每个元素最多使用k次”的LIS变种中，通常是指：原数组提供了每个元素，但你可以从原数组中重复选取同一个元素（想象你有无穷多个相同的数字可用），但每个值在整个子序列中最多出现 `k `` 次。但这样问题就退化到对值的计数了，不是动态规划。另一种常见变种是：你有一个序列，每个位置i的元素可以被使用最多k次（但位置是唯一的，这说不通）。我们设定一个经典变种：给你一个数组 nums ，你可以从数组中删除一些元素（也可以不删除），形成一个新序列，但要求新序列是非递减的，并且原数组中每个位置的元素不能被重复使用（每个位置最多用一次），但是数组里可能有重复值。现在额外增加一个限制：在生成的子序列中，任何值最多可以出现 k 次。注意，这是对子序列中值出现频率的限制，而不是对原数组元素使用次数的限制（原数组每个位置只能用一次）。举个例子： nums = [1, 2, 2, 3, 3, 3, 4], k = 2 原数组有多个重复值。最长非递减子序列可以是 [1, 2, 2, 3, 3, 4] ，其中2出现了2次，3出现了2次，没有超过k=2。但你不能取三个3，因为值3最多出现2次。所以最终长度是6。你的任务是计算满足以下条件的最长子序列的长度：子序列是非递减的（即 a[i] <= a[i+1] ）。在子序列中，任何值 v 出现的次数不超过 k 。注意：子序列不要求连续，可以从原数组删除任意元素得到，但顺序需保持原顺序。解题思路这是一个带限制的最长非递减子序列（LNDS）问题。如果没有k的限制，就是经典的LIS（非递减版），可以用O(n²)动态规划或O(n log n)的贪心+二分查找。但有了“每个值最多出现k次”的限制，我们需要在状态中记录当前子序列末尾的值以及该值已连续（或在整体中）出现了多少次。关键观察：由于子序列要求非递减，当我们往子序列中添加一个数字x时，如果x大于当前末尾值，那么添加后x的出现次数重置为1（因为这是一个新的值开始）。如果x等于当前末尾值，那么x的出现次数加1，但不能超过k。所以我们需要在状态中记录：当前考虑到了原数组的哪个位置 i 。当前子序列的最后一个值 lastVal 。当前子序列中末尾这个值 lastVal 已经连续出现了多少次 cnt （注意，因为是非递减，所以末尾连续相同值就是整个子序列中这个值出现的总次数，因为相同的值只会连续出现，不会在中间插入其他值后再出现相同的值，否则就不是非递减了。但如果我们允许子序列是 [1,2,1] 吗？不允许，因为1再次出现时，前面的2比1大，序列不是非递减。所以，相同值在非递减子序列中必然是连续的一段。因此，我们只需要记录末尾值的连续出现次数，也就等于这个值在子序列中出现的总次数）。但是， lastVal 的可能取值很多（如果数字范围大）。我们需要状态压缩。一个常见技巧是：我们并不需要精确知道 lastVal 是多少，只需要知道它是原数组中的某个值，而且当我们决定在子序列末尾添加 nums[i] 时，我们需要判断 nums[i] 与 lastVal 的大小关系。因此，我们可以将状态设计为： dp[i][c] 表示以原数组第 i 个元素结尾的子序列，并且这个子序列末尾的值（即 nums[i] ）在该子序列中连续出现了 c 次（显然 1 <= c <= k ）时，所能得到的最长子序列长度。状态转移：当我们考虑以 i 结尾的子序列，且末尾值出现了 c 次，那么这个子序列的倒数第二个元素可能是某个 j < i 且 nums[j] <= nums[i] 。但还需要满足：如果 nums[j] < nums[i] ，那么添加 nums[i] 后， nums[i] 是新的值，所以 c 必须是1（即 nums[i] 第一次出现）。如果 nums[j] == nums[i] ，那么添加 nums[i] 后，末尾相同值的出现次数从 c-1 增加到了 c ，所以前一个状态是以 j 结尾且末尾值出现次数为 c-1 的子序列。因此，转移方程可以写为：如果 c == 1 ： dp[i][1] = 1 + max{ dp[j][*] } 对所有 j < i 且 nums[j] <= nums[i] ，这里 * 表示从1到k的任何次数，但注意必须满足 nums[j] < nums[i] 或者 nums[j] == nums[i] 但此时 c 必须是1，所以实际上当 c=1 时， nums[i] 是新值，所以前一个结尾的值必须小于 nums[i] （不能等于，因为等于的话就会使相同值次数>1）。所以条件应该是 nums[j] < nums[i] 。另外，也可以没有前一个元素，即单独以 i 开头，长度为1。如果 c > 1 ：那么前一个元素必须等于 nums[i] ，且前一个状态中末尾值的出现次数是 c-1 。即 dp[i][c] = 1 + dp[j][c-1] 对某个 j < i 且 nums[j] == nums[i] 。同样，也可以从自己开始，但 c>1 时自己开始不可能，因为单个元素c=1。然而，这个动态规划复杂度是 O(n² * k)，在n较大时会超时。我们需要优化。优化思路：注意到，我们需要快速查询：对于 c=1 ：所有 j < i 且 nums[j] < nums[i] 的 max(dp[j][*]) 。对于 c>1 ：所有 j < i 且 nums[j] == nums[i] 的 dp[j][c-1] 。我们可以用数据结构来维护：对每个不同的值 v ，维护一个数组 best[v][c] 表示以值 v 结尾，且末尾值出现次数为 c 时的最大子序列长度。但我们需要按原数组顺序更新，所以当处理到 i 时，我们需要查询所有值小于 nums[i] 的 max(best[小于v][*]) ，以及值等于 nums[i] 的 best[nums[i]][c-1] 。因为值的范围可能很大，我们可以对值进行离散化（排序+去重）。然后用树状数组（Fenwick Tree）或线段树来维护前缀最大值（对离散化后的值）。具体地，我们维护 k 个树状数组 BIT[c] ，其中 BIT[c] 存储：以某个值 v 结尾，且末尾值出现次数为 c 时的最大长度。这样，当计算 dp[i][c] 时：如果 c=1 ：我们需要查询所有值严格小于 nums[i] 的各个次数下的最大长度，即 max_{v < nums[i]} max_{t=1..k} BIT[t].query(v-1) 。我们可以额外维护一个“全局”树状数组 BIT_all ，它存储每个值 v 在所有次数下的最大长度，即 max_{t=1..k} best[v][t] 。那么 dp[i][1] = 1 + BIT_all.query(rank(nums[i])-1) ，其中 rank 是离散化后的秩（1-based）。如果查询为空，则 dp[ i][ 1 ]=1。如果 c>1 ：我们需要查询值等于 nums[i] 且次数为 c-1 的最大长度，即 dp[i][c] = 1 + best[nums[i]][c-1] ，其中 best[nums[i]][c-1] 是之前计算过的、以值 nums[i] 结尾且次数为 c-1 的最大长度。注意，可能有多个位置 j 都以值 nums[i] 结尾，我们取最大的那个长度作为 best[nums[i]][c-1] 。在计算完 dp[i][c] 后，我们需要更新 best[nums[i]][c] 为 max(best[nums[i]][c], dp[i][c]) ，并相应更新树状数组 BIT_all 在值 nums[i] 处的值为 max(BIT_all.query(rank(nums[i])), dp[i][c]) （实际上 BIT_ all 存储的是这个值所有次数下的最大值，所以我们更新时需要用新的最大值去更新，但树状数组通常支持单点更新为更大值，需要先查询当前值，如果新值更大才更新）。算法步骤：离散化：将 nums 中所有值去重排序，得到每个值对应的秩 id ，从1到m。初始化：创建两个数组（或字典） best[m+1][k+1] ，全部置0。创建树状数组 BIT_all 大小为 m+1，初始为0。按顺序遍历原数组 nums 的每个元素 x ，设其离散化秩为 idx 。先计算 c=1 的情况： len1 = 1 + BIT_all.query(idx-1) 。如果查询为0，则 len1=1 。然后计算 c=2..k 的情况： lenc = 1 + best[idx][c-1] 。注意，如果 best[idx][c-1]==0 ，说明之前没有以值x结尾且次数为c-1的子序列，那么 lenc 应该为0（无效）。实际上， lenc 的有效性要求 best[idx][c-1] > 0 。对于每个 c=1..k ，如果计算出的长度 dp_c 大于0，则更新 best[idx][c] = max(best[idx][c], dp_c) ，并更新树状数组：查询当前 BIT_ all 在 idx 位置的值 old = BIT_all.point_query(idx) ，如果 dp_c > old ，则执行 BIT_all.update(idx, dp_c) 。最终答案是所有 best[i][c] 中的最大值，以及 BIT_all.query(m) 的最大值（其实 BIT_ all 的全局最大值就是答案）。复杂度：遍历数组 n 次，内层循环 k 次，每次树状数组操作 O(log m)，总复杂度 O(nk log m)，其中 m 是不同值的个数。如果 k 较小，可以接受。边界情况：如果 k=1，那么就是标准的严格递增子序列（因为相同值不能出现超过1次，但题目要求非递减，所以实际上不允许相等，等同于严格递增）。但注意，如果原题要求非递减，k=1 时意味着不允许重复值，所以等价于严格递增。如果 k >= n，那么相当于没有限制，就是标准的非递减子序列（LNDS），可以用 O(n log n) 的贪心算法，但这里我们的算法也能工作，只是复杂度稍高。例子： nums = [1,2,2,3,3,3,4], k=2 离散化值：{1:1, 2:2, 3:3, 4:4} 初始化 best[ 5][ 3]=0, BIT_ all[ 5 ]=0. i=0, x=1, idx=1 c=1: BIT_ all.query(0)=0 -> len1=1 c=2: best[ 1][ 1 ]=0 -> len2=0 (无效) 更新 best[ 1][ 1]=1, BIT_ all.update(1,1) i=1, x=2, idx=2 c=1: BIT_ all.query(1)=1 -> len1=2 c=2: best[ 2][ 1 ]=0 -> len2=0 更新 best[ 2][ 1]=2, BIT_ all.update(2,2) i=2, x=2, idx=2 c=1: BIT_ all.query(1)=1 -> len1=2 c=2: best[ 2][ 1 ]=2 -> len2=3 更新 best[ 2][ 1]=max(2,2)=2, best[ 2][ 2]=3, BIT_ all.update(2,3) (因为3>2) i=3, x=3, idx=3 c=1: BIT_ all.query(2)=3 -> len1=4 c=2: best[ 3][ 1 ]=0 -> len2=0 更新 best[ 3][ 1]=4, BIT_ all.update(3,4) i=4, x=3, idx=3 c=1: BIT_ all.query(2)=3 -> len1=4 c=2: best[ 3][ 1 ]=4 -> len2=5 更新 best[ 3][ 1]=4, best[ 3][ 2]=5, BIT_ all.update(3,5) i=5, x=3, idx=3 c=1: BIT_ all.query(2)=3 -> len1=4 c=2: best[ 3][ 2 ]=5 -> len2=6 但注意，c=2 时，我们要求末尾值出现次数为2，前一个状态末尾值出现次数为1，且值相等。best[ 3][ 2]=5 表示之前有长度为5且以3结尾出现2次的子序列。现在再加一个3，那么末尾值出现次数变为3，但 k=2 不允许出现3次，所以 c=3 不允许。所以这里 c=2 已经达到上限，不能再增加。实际上，当 c>k 时我们不考虑。所以对于 i=5, x=3, 我们只能计算 c=1,2。c=2 时，len2=1+best[ 3][ 1]=1+4=5，与之前一样。c=1 时 len1=4。所以没有更长的。但注意，我们之前已经有 best[ 3][ 2 ]=5，现在又得到5，不变。更新：best[ 3][ 1] 保持4，best[ 3][ 2]保持5，BIT_ all不变。 i=6, x=4, idx=4 c=1: BIT_ all.query(3)=5 -> len1=6 c=2: best[ 4][ 1 ]=0 -> len2=0 更新 best[ 4][ 1]=6, BIT_ all.update(4,6) 最终最大值为6，对应子序列 [ 1,2,2,3,3,4] 或 [ 1,2,2,3,3,4 ] 等。总结：这个算法通过树状数组优化了小于当前值的查询，并通过 best 数组记录了相同值的状态，实现了 O(nk log m) 的时间复杂度。如果 k 较小，这是一个高效的解法。注意，如果 k 很大（比如 k>=n），我们可以退化成普通的 LIS 贪心算法，但这里不展开。扩展：这个问题的变种可以改成“每个值最多出现 k 次，但不要求连续”，但在非递减子序列中，相同值必然连续，所以没有区别。如果原题是严格递增，那么相同值不允许出现，k 限制就没有意义（除非 k>=1）。所以本题设定为非递减是合理的。希望这个讲解能让你理解这个线性动态规划问题的解法。