Find the Maximum Length of a Good Subsequence II

Find the Maximum Length of a Good Subsequence II

What is this problem about?

This is the "Hard" version of the previous problem. In Find the Maximum Length of a Good Subsequence II, the constraints on $N$ and $K$ are much larger. You still need to find the longest subsequence with at most $k$ adjacent differences, but you must optimize the transitions to avoid $O(N^2 imes K)$ complexity.

Why is this asked in interviews?

Snowflake uses this to evaluate a candidate's ability to optimize Dynamic Programming transitions. It tests your mastery of using auxiliary data structures (like Hash Maps or running maximums) to convert an $O(N^2 imes K)$ solution into $O(N imes K)$. It evaluations whether you can identify that for a fixed number of changes $j$, you only need the "best previous length" from any number and the "best previous length" from the same number.

Algorithmic pattern used

This problem uses DP with Optimization (Caching Maximums).

1. Maintain dp[val][j] which is the max length ending with value val and j changes.
2. Maintain max_for_changes[j] which is the max length across any value with j changes.
3. When processing nums[i]:
   • Option 1 (No change): new_len = dp[nums[i]][j] + 1.
   • Option 2 (One change): new_len = max_for_changes[j-1] + 1.
4. Update dp[nums[i]][j] and max_for_changes[j] with the maximum of these options.
5. This reduces the complexity to $O(N imes K)$.

Example explanation

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

1. For 1: dp[1][0] = 1, max[0] = 1.
2. For 2:
   • j=0: dp[2][0] = 1, max[0] = 1.
   • j=1: new = max[0] + 1 = 2. dp[2][1] = 2, max[1] = 2.
3. For next 1:
   • j=0: new = dp[1][0] + 1 = 2. dp[1][0] = 2, max[0] = 2.
   • j=1: new = max(dp[1][1]+1, max[0]+1) = max(1, 3) = 3. dp[1][1] = 3, max[1] = 3. The logic continues, achieving linear time per change count.

Common mistakes candidates make

• Redundant States: Storing the full $N imes K$ table when only the current max per value is needed.
• Update Order: Not processing $j$ from $k$ down to 0 (or using a temporary variable) to avoid using the "current" element's updated value for the same step.
• Complexity: Failing to use the max_for_changes array, which is the key to the $O(N imes K)$ optimization.

Interview preparation tip

Master the "Max of previous" optimization in DP. Whenever you find yourself writing a loop for p in 0...i-1 inside a DP, ask if you can replace that loop with a single $O(1)$ lookup from a precomputed maximum or a Hash Map. This is the hallmark of a senior-level algorithmic candidate.