Find the Maximum Length of Valid Subsequence II

Find the Maximum Length of Valid Subsequence II

What is this problem about?

This is the generalized version of the previous problem. In Find the Maximum Length of Valid Subsequence II, a subsequence is valid if the sum of every adjacent pair $(sub[i] + sub[i+1])$ modulo $k$ is the same constant. You are given an array and an integer $k$, and you need to find the longest valid subsequence.

Why is this asked in interviews?

Uber and Google use this to test your mastery of Dynamic Programming. Unlike version I where $k=2$, here $k$ can be larger, requiring a more robust DP approach. It evaluations whether you can define a 2D state that tracks the last element and the target sum, and whether you can optimize the transitions to avoid $O(N^2)$ checks.

Algorithmic pattern used

This problem is solved using Dynamic Programming.

1. Define dp[rem][target] as the maximum length of a subsequence ending with a number whose remainder is rem, where the target sum of adjacent pairs modulo $k$ is target.
2. For each number $X$ in the array:
   • Let remX = X % k.
   • Iterate through all possible target sums T from 0 to $k-1$.
   • The required remainder of the previous element would be prevRem = (T - remX + k) % k.
   • dp[remX][T] = dp[prevRem][T] + 1.
3. The answer is the maximum value in the dp table.

Example explanation

nums = [1, 4, 2, 3], $k = 3$. Target Sum $T=2$:

1. Number 1: rem=1. prevRem = (2-1) = 1. dp[1][2] = dp[1][2] + 1 = 1.
2. Number 4: rem=1. prevRem = (2-1) = 1. dp[1][2] = 1 + 1 = 2.
3. Number 2: rem=2. prevRem = (2-2) = 0. dp[2][2] = dp[0][2] + 1 = 1.
4. Number 3: rem=0. prevRem = (2-0) = 2. dp[0][2] = dp[2][2] + 1 = 2. Final result is the max across all $T$.

Common mistakes candidates make

• Inefficient state: Trying to use dp[i][j] (indices), leading to $O(N^2)$ complexity.
• Modular arithmetic: Not handling negative results correctly (always add $k$ before modulo).
• Missing cases: Not iterating through all possible target sums $T$.

Interview preparation tip

In DP problems involving subsequences and modular sums, the "remainder" of the last element is almost always part of the state. If the condition involves pairs, the state must link the current remainder to the previous one via the condition (the target sum).