针对 LeetCode 3177. 求出最长好序列 IIC 的实现逻辑与 Java 完全一致但我们可以利用 C 的 unordered_map 和数组特性写出运行效率更高的代码。核心思路回顾1. 状态定义dp[x][j] 表示以数值 x 结尾且恰好有 j 个相邻不同元素坏对的最长好子序列长度。2. 状态转移- 延续相同数字或接续其他数字的最优解dp[x][j] max(dp[x][j], globalMax[j]) 1。- 更新全局最优globalMax[j 1] max(globalMax[j 1], dp[x][j])。3. 关键细节内层循环必须从 k 倒序遍历到 0。如果正序遍历globalMax[j] 会在当前数字处理到 j-1 时被提前更新导致同一位置的数字被重复选取相当于把坏对数量算错了。C 代码实现class Solution {public:int maximumLength(vectorint nums, int k) {// dp: key为数组中的值value为长度为k1的vector表示以该值结尾、包含0~k个不同相邻对的最大长度unordered_mapint, vectorint dp;// globalMax[j]: 记录当前所有数字中以恰好 j-1 个不同相邻对结尾的最大子序列长度// 使用 k2 的大小是为了防止越界且方便统一索引globalMax[j1] 对应 j 个坏对vectorint globalMax(k 2, 0);for (int x : nums) {// 如果当前数字第一次出现初始化其对应的dp数组全为0if (!dp.count(x)) {dp[x] vectorint(k 1, 0);}auto curDp dp[x]; // 使用引用避免哈希表查找和拷贝开销// 必须从 k 倒序遍历到 0避免本轮更新的数据污染后续状态的转移for (int j k; j 0; --j) {// 状态转移取“延续相同数字(curDp[j])”和“接续不同数字(globalMax[j])”中的最大值然后 1curDp[j] max(curDp[j], globalMax[j]) 1;// 更新全局最大值// curDp[j] 代表以 x 结尾且有 j 个坏对存入 globalMax[j1]globalMax[j 1] max(globalMax[j 1], curDp[j]);}}// globalMax[k1] 即为包含最多 k 个不同相邻对的最大长度return globalMax[k 1];}};C 性能优化点说明1. 引用传递 (auto curDp dp[x];)直接获取哈希表中 vector 的引用避免了每次循环都进行哈希查找和对象拷贝。2. 内存预分配在初始化 dp[x] 时直接使用 vectorint(k 1, 0)避免了动态扩容带来的额外开销。3. 前置自减 (--j)在循环中使用 --j 代替 j--在某些老旧编译器下能略微减少临时变量的生成现代编译器通常会自动优化。复杂度分析- 时间复杂度O(N times K)遍历 N 个元素每个元素内部执行 K 次常数时间操作。- 空间复杂度O(U times K)U 为数组中不同元素的个数最坏情况下退化为 O(N times K)。