Skip to content

3202. Find the Maximum Length of Valid Subsequence II 👍

  • Time: $O(k^2 + nk)$
  • Space: $O(k^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  // Similar to 3201. Find the Maximum Length of Valid Subsequence I
  int maximumLength(vector<int>& nums, int k) {
    // dp[i][j] := the maximum length of a valid subsequence, where the last
    // number mod k equal to i and the next desired number mod k equal to j
    vector<vector<int>> dp(k, vector<int>(k));

    // Extend the pattern xyxyxy...xy.
    for (const int x : nums)
      for (int y = 0; y < k; ++y)
        dp[x % k][y] = dp[y][x % k] + 1;

    return accumulate(dp.begin(), dp.end(), 0,
                      [](int acc, const vector<int>& row) {
      return max(acc, ranges::max(row));
    });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  // Similar to 3201. Find the Maximum Length of Valid Subsequence I
  public int maximumLength(int[] nums, int k) {
    // dp[i][j] := the maximum length of a valid subsequence, where the last
    // number mod k equal to i and the next desired number mod k equal to j
    int[][] dp = new int[k][k];

    // Extend the pattern xyxyxy...xy.
    for (final int x : nums)
      for (int y = 0; y < k; ++y)
        dp[x % k][y] = dp[y][x % k] + 1;

    return Arrays.stream(dp).flatMapToInt(Arrays::stream).max().getAsInt();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  # Similar to 3201. Find the Maximum Length of Valid Subsequence I
  def maximumLength(self, nums: list[int], k: int) -> int:
    # dp[i][j] := the maximum length of a valid subsequence, where the last
    # number mod k equal to i and the next desired number mod k equal to j
    dp = [[0] * k for _ in range(k)]

    # Extend the pattern xyxyxy...xy.
    for x in nums:
      for y in range(k):
        dp[x % k][y] = dp[y][x % k] + 1

    return max(map(max, dp))