Find the Maximum Length of a Good Subsequence I

Find the Maximum Length of a Good Subsequence I

What is this problem about?

In the Find the Maximum Length of a Good Subsequence I coding problem, a subsequence is called "good" if the number of indices $i$ such that $sub[i] eq sub[i+1]$ is at most $k$. You are given an array of integers and an integer $k$, and you need to find the length of the longest good subsequence.

Why is this asked in interviews?

Snowflake asks this to test your proficiency with Dynamic Programming interview patterns. It evaluations whether you can define a state that captures both the current element being considered and the number of "changes" used so far. It’s a test of how you handle transitions where you either continue a sequence of identical numbers or start a new sequence at the cost of one "change."

Algorithmic pattern used

This problem is solved using Dynamic Programming.

1. Define dp[i][j] as the maximum length of a good subsequence ending at index i with exactly j changes.
2. Transition:
   • If we append nums[i] to a subsequence ending at some p < i:
     • If nums[i] == nums[p], the number of changes doesn't increase: dp[i][j] = max(dp[i][j], dp[p][j] + 1).
     • If nums[i] != nums[p], the number of changes increases by 1: dp[i][j] = max(dp[i][j], dp[p][j-1] + 1).
3. The answer is the maximum value in the dp table.

Example explanation

nums = [1, 2, 1, 1, 3], $k = 1$.

1. We can pick [1, 1, 1] (0 changes, length 3).
2. We can pick [1, 1, 1, 3] (1 change at the end, length 4).
3. We can pick [1, 2, 1, 1] (1 change after '2', length 4). Max length: 4.

Common mistakes candidates make

• Incorrect State: Forgetting to include the count of changes in the DP state.
• $O(N^3)$ complexity: Using a nested loop over p inside the j loop, which is $O(N^2 imes K)$. While acceptable for Version I, it’s not optimal.
• Initialization: Failing to initialize the dp table with 1 (since any single element is a valid subsequence of length 1 with 0 changes).

Interview preparation tip

When a problem involves a "at most $K$ changes" or "at most $K$ exceptions" constraint, it almost always points to a DP state where $K$ is one of the dimensions. Practice optimizing these DP transitions using running maximums or Hash Maps to achieve better complexity.