Find the maximum length of valid subsequence i

Array Dynamic Programming

54.9% acceptance

Feb 25, 2026

639

You are given an integer array nums. A subsequence sub of nums with length x is called valid if it satisfies: (sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2. Return the length of the longest valid subsequence of nums. A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_length(nums: Vec<i32>) -> i32 {
    // count[p] = count of elements with parity p (same-parity subsequences)
    let mut count = [0i32; 2];
    // dp[p] = longest alternating subsequence ending with parity p
    let mut dp = [0i32; 2];
    for &x in &nums {
      let p = (x % 2) as usize;
      count[p] += 1;
      dp[p] = dp[1 - p] + 1;
    }
    *[count[0], count[1], dp[0], dp[1]].iter().max().unwrap()
  }
}