Skip to content

3201. Find the Maximum Length of Valid Subsequence I 👍

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

    // Extend the pattern xyxyxy...xy.
    for (const int x : nums)
      for (int y = 0; y < 2; ++y)
        dp[x % 2][y] = dp[y][x % 2] + 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
class Solution {
  public int maximumLength(int[] nums) {
    // dp[i][j] := the maximum length of a valid subsequence, where the last
    // number mod 2 equal to i and the next desired number mod 2 equal to j
    int[][] dp = new int[k][k];

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def maximumLength(self, nums: list[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] * 2 for _ in range(2)]

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

    return max(map(max, dp))