#3176

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the Maximum Length of a Good Subsequence I

Find the maximum length of a good subsequence by scanning arrays and using hash lookups for value remapping efficiently.

array hash table dynamic programming

Problem Statement

You are given an integer array nums and a non-negative integer k. A subsequence is called good if it contains at most k positions where consecutive elements differ. Determine the maximum length of such a good subsequence within nums.

For example, given nums = [1,2,1,1,3] and k = 2, the subsequence [1,2,1,1,3] contains at most two positions where consecutive elements differ, achieving the maximum length possible. Return the length of the longest good subsequence under the given constraint.

Examples

Example 1

Input: nums = [1,2,1,1,3], k = 2

Output: 4

The maximum length subsequence is [ 1 , 2 , 1 , 1 ,3] .

Example 2

Input: nums = [1,2,3,4,5,1], k = 0

Output: 2

The maximum length subsequence is [ 1 ,2,3,4,5, 1 ] .

Constraints

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

Solution Approach

Remap Array Values

Map all unique values in nums to a contiguous range [0, n-1] so differences can be tracked with a fixed-size hash table, reducing overhead in dynamic programming.

Track Differences with Hash Table

Use a hash table to count consecutive differences while iterating through nums. Increment counts only when differences occur and stop adding if the limit k is reached.

Dynamic Programming on Lengths

Apply dynamic programming to store the maximum good subsequence length ending at each value. Update lengths by considering allowed differences and previously computed subsequences.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Dynamic Programming

We define $f[i][h]$ as the length of the longest good subsequence ending with $nums[i]$ and having no more than $h$ indices satisfying the condition. Initially, $f[i][h] = 1$. The answer is $\max(f[i][k])$, where $0 \le i < n$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

Solution 2: Optimized Dynamic Programming

According to the state transition equation in Solution 1, if $nums[i] = nums[j]$, then we only need to get the maximum value of $f[j][h]$. We can maintain this with an array $mp$ of length $k + 1$. If $nums[i] \neq nums[j]$, we need to record the maximum value of $f[j][h - 1]$ corresponding to $nums[j]$, the maximum value and the second maximum value. We can maintain these with an array $g$ of length $k + 1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

Continue Practicing

#3177 find the maximum length of a good subsequence ii #3186 maximum total damage with spell casting #3316 find maximum removals from source string