千问 LeetCode 3177. 求出最长好子序列 II Java实现

针对 LeetCode 3177. 求出最长好子序列 II由于数据规模较大常规的动态规划如三重循环或双重循环会导致超时。我们需要使用 哈希表 动态规划 前缀和全局最大值优化 来将时间复杂度降至 O(N times K)。核心思路1. 状态定义定义 dp[x][j] 表示以数值 x 结尾且恰好有 j 个相邻不同元素坏对的最长好子序列长度。2. 状态转移- 如果当前数字 x 与上一个数字相同则不增加坏对数量dp[x][j] dp[x][j] 1。- 如果当前数字 x 与上一个数字不同则坏对数量加 1dp[x][j] max(dp[y][j-1]) 1其中 y ! x。3. 优化- 使用哈希表HashMap存储以各个数值结尾的状态避免遍历整个数组。- 维护一个数组 globalMax[j]记录所有数值中坏对数量为 j 时的最长子序列长度。这样在遇到不同数字时可以直接通过 globalMax[j-1] 1 获取最优解省去遍历其他数值的开销。- 在更新哈希表时需从后往前从 k 到 0遍历 j防止同一轮次的数据被重复使用。Java 代码实现class Solution {public int maximumLength(int[] nums, int k) {// dp: key为数组中的值value为长度为k1的数组表示以该值结尾、包含0~k个不同相邻对的最大长度MapInteger, int[] dp new HashMap();// globalMax[j]: 记录当前所有数字中以恰好 j 个不同相邻对结尾的最大子序列长度int[] globalMax new int[k 2];for (int x : nums) {// 如果当前数字第一次出现初始化其对应的dp数组if (!dp.containsKey(x)) {dp.put(x, new int[k 1]);}int[] curDp dp.get(x);// 必须从 k 倒序遍历到 0避免本轮更新的数据影响后续状态的转移for (int j k; j 0; j--) {// 状态转移取“延续相同数字”和“接续不同数字”中的最大值然后 1// globalMax[j] 已经包含了相同数字的情况因为 f(x,j) f(x,j-1)curDp[j] Math.max(curDp[j], globalMax[j]) 1;// 更新全局最大值注意对应到 globalMax 的索引需要 1globalMax[j 1] Math.max(globalMax[j 1], curDp[j]);}}// 返回包含最多 k 个不同相邻对的最大长度return globalMax[k 1];}}复杂度分析- 时间复杂度O(N times K)其中 N 是数组 nums 的长度。对于每个元素我们只需要在内层循环中遍历 K 次即可完成状态转移。- 空间复杂度O(U times K)其中 U 是数组 nums 中不同数字的个数最坏情况下为 O(N times K)。