What defines a good subsequence in this problem?

A good subsequence has at most k indices where consecutive elements differ, allowing limited changes.

How does array scanning plus hash lookup help here?

It tracks counts of consecutive differences efficiently and lets you quickly update maximum subsequence lengths.

Can the solution handle large nums values?

Yes, by remapping all values to a range [0, n-1], we avoid large hash table sizes and simplify DP updates.

What happens if k = 0?

Only consecutive identical elements can form a good subsequence, so the maximum length comes from repeated values.

Is dynamic programming necessary for Find the Maximum Length of a Good Subsequence I?

DP is helpful to efficiently propagate maximum lengths while respecting the k differences constraint, reducing redundant scans.

#3176

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

求出最长好子序列 I

给你一个整数数组 nums 和一个非负整数 k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中最多只有 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为好序列。请你返回 nums 中好子序列的最长长度…

数组哈希表动态规划

题目描述

给你一个整数数组 nums 和一个非负整数 k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为好序列。

请你返回 nums 中好子序列的最长长度。

示例 1：

输入：nums = [1,2,1,1,3], k = 2

输出：4

解释：

最长好子序列为 [1,2,1,1,3] 。

示例 2：

输入：nums = [1,2,3,4,5,1], k = 0

输出：2

解释：

最长好子序列为 [1,2,3,4,5,1] 。

提示：

1 <= nums.length <= 500
1 <= nums[i] <= 10⁹
0 <= k <= min(nums.length, 25)

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][h]$ 表示以 $nums[i]$ 结尾，且有不超过 $h$ 个下标满足条件的最长好子序列的长度。初始时 $f[i][h] = 1$ 。答案为 $\max(f[i][k])$ ，其中 $0 \le i < n$ 。

我们考虑如何计算 $f[i][h]$ 。我们可以枚举 $0 \le j < i$ ，如果 $nums[i] = nums[j]$ ，那么 $f[i][h] = \max(f[i][h], f[j][h] + 1)$ ；否则如果 $h > 0$ ，那么 $f[i][h] = \max(f[i][h], f[j][h - 1] + 1)$ 。即：

f[i][h]= \begin{cases} \max(f[i][h], f[j][h] + 1), & \textit{if } nums[i] = nums[j], \\ \max(f[i][h], f[j][h - 1] + 1), & \textit{if } h > 0. \end{cases}

最终答案为 $\max(f[i][k])$ ，其中 $0 \le i < n$ 。

时间复杂度 $O(n^2 \times k)$ ，空间复杂度 $O(n \times k)$ 。其中 $n$ 是数组 nums 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        f = [[1] * (k + 1) for _ in range(n)]
        ans = 0
        for i, x in enumerate(nums):
            for h in range(k + 1):
                for j, y in enumerate(nums[:i]):
                    if x == y:
                        f[i][h] = max(f[i][h], f[j][h] + 1)
                    elif h:
                        f[i][h] = max(f[i][h], f[j][h - 1] + 1)
            ans = max(ans, f[i][k])
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on scanning nums once and updating hash table entries for each element, roughly O(n) with n as array length. Space complexity is dominated by the hash table or DP array, O(n) in the worst case.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check whether consecutive differences are correctly bounded by k.
question_mark
Ensure remapping reduces the value range to simplify hash table usage.
question_mark
Confirm that dynamic programming correctly propagates maximum lengths without exceeding k differences.

warning

常见陷阱

外企场景

error
Failing to remap values, leading to unnecessary large hash tables.
error
Overcounting consecutive differences and exceeding k, producing incorrect lengths.
error
Ignoring edge cases where k = 0 or nums has repeated elements only.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the minimum number of changes required to make the longest good subsequence reach a target length.
arrow_right_alt
Modify the problem to allow up to k consecutive differences per segment rather than entire sequence.
arrow_right_alt
Consider a version where nums contains negative values, requiring careful remapping for hash table indexing.

help

常见问题

外企场景

继续练习

#3177 求出最长好子序列 II #3186 施咒的最大总伤害 #3316 从原字符串里进行删除操作的最多次数