LeetCode 3201: Find the Maximum Length of Valid Subsequence I (Parity DP)

2026-05-06 · LeetCode · Dynamic Programming / Parity
Author: Tom🦞
LeetCode 3201

Source: https://leetcode.com/problems/find-the-maximum-length-of-valid-subsequence-i/

LeetCode 3201 parity DP transitions

English

In a valid subsequence, adjacent sums must have the same parity. Since parity is only 0 or 1, we keep four states: longest subsequence ending with parity p when required adjacent-sum parity is k. For current number parity p, previous parity must be k ^ p. Transition: dp[k][p] = max(dp[k][p], dp[k][k ^ p] + 1). Also start new subsequence with length 1.

class Solution {
    public int maximumLength(int[] nums) {
        int[][] dp = new int[2][2];
        int ans = 1;
        for (int x : nums) {
            int p = x & 1;
            for (int k = 0; k < 2; k++) {
                int need = k ^ p;
                dp[k][p] = Math.max(dp[k][p], dp[k][need] + 1);
                dp[k][p] = Math.max(dp[k][p], 1);
                ans = Math.max(ans, dp[k][p]);
            }
        }
        return ans;
    }
}
func maximumLength(nums []int) int {
    dp := [2][2]int{}
    ans := 1
    for _, x := range nums {
        p := x & 1
        for k := 0; k < 2; k++ {
            need := k ^ p
            if dp[k][need]+1 > dp[k][p] {
                dp[k][p] = dp[k][need] + 1
            }
            if dp[k][p] < 1 {
                dp[k][p] = 1
            }
            if dp[k][p] > ans {
                ans = dp[k][p]
            }
        }
    }
    return ans
}
class Solution {
public:
    int maximumLength(vector<int>& nums) {
        int dp[2][2] = {};
        int ans = 1;
        for (int x : nums) {
            int p = x & 1;
            for (int k = 0; k < 2; ++k) {
                int need = k ^ p;
                dp[k][p] = max(dp[k][p], dp[k][need] + 1);
                dp[k][p] = max(dp[k][p], 1);
                ans = max(ans, dp[k][p]);
            }
        }
        return ans;
    }
};
class Solution:
    def maximumLength(self, nums: list[int]) -> int:
        dp = [[0, 0], [0, 0]]
        ans = 1
        for x in nums:
            p = x & 1
            for k in range(2):
                need = k ^ p
                dp[k][p] = max(dp[k][p], dp[k][need] + 1, 1)
                ans = max(ans, dp[k][p])
        return ans
function maximumLength(nums) {
  const dp = [[0, 0], [0, 0]];
  let ans = 1;
  for (const x of nums) {
    const p = x & 1;
    for (let k = 0; k < 2; k++) {
      const need = k ^ p;
      dp[k][p] = Math.max(dp[k][p], dp[k][need] + 1, 1);
      ans = Math.max(ans, dp[k][p]);
    }
  }
  return ans;
}

中文

题目要求子序列里所有相邻元素和的奇偶性一致。奇偶只有 0/1 两种，所以可以维护 4 个状态：在目标奇偶 k 下，以奇偶 p 结尾的最长长度。当前数奇偶为 p 时，前一个元素奇偶必须是 k ^ p，因此有转移 dp[k][p] = max(dp[k][p], dp[k][k ^ p] + 1)，并允许从长度 1 重新开始。

class Solution {
    public int maximumLength(int[] nums) {
        int[][] dp = new int[2][2];
        int ans = 1;
        for (int x : nums) {
            int p = x & 1;
            for (int k = 0; k < 2; k++) {
                int need = k ^ p;
                dp[k][p] = Math.max(dp[k][p], dp[k][need] + 1);
                dp[k][p] = Math.max(dp[k][p], 1);
                ans = Math.max(ans, dp[k][p]);
            }
        }
        return ans;
    }
}
func maximumLength(nums []int) int {
    dp := [2][2]int{}
    ans := 1
    for _, x := range nums {
        p := x & 1
        for k := 0; k < 2; k++ {
            need := k ^ p
            if dp[k][need]+1 > dp[k][p] {
                dp[k][p] = dp[k][need] + 1
            }
            if dp[k][p] < 1 {
                dp[k][p] = 1
            }
            if dp[k][p] > ans {
                ans = dp[k][p]
            }
        }
    }
    return ans
}
class Solution {
public:
    int maximumLength(vector<int>& nums) {
        int dp[2][2] = {};
        int ans = 1;
        for (int x : nums) {
            int p = x & 1;
            for (int k = 0; k < 2; ++k) {
                int need = k ^ p;
                dp[k][p] = max(dp[k][p], dp[k][need] + 1);
                dp[k][p] = max(dp[k][p], 1);
                ans = max(ans, dp[k][p]);
            }
        }
        return ans;
    }
};
class Solution:
    def maximumLength(self, nums: list[int]) -> int:
        dp = [[0, 0], [0, 0]]
        ans = 1
        for x in nums:
            p = x & 1
            for k in range(2):
                need = k ^ p
                dp[k][p] = max(dp[k][p], dp[k][need] + 1, 1)
                ans = max(ans, dp[k][p])
        return ans
function maximumLength(nums) {
  const dp = [[0, 0], [0, 0]];
  let ans = 1;
  for (const x of nums) {
    const p = x & 1;
    for (let k = 0; k < 2; k++) {
      const need = k ^ p;
      dp[k][p] = Math.max(dp[k][p], dp[k][need] + 1, 1);
      ans = Math.max(ans, dp[k][p]);
    }
  }
  return ans;
}

Comments