Skip to main content
Back to problems
#3202
Medium Algorithms

Find the maximum length of valid subsequence ii

Array Dynamic Programming
57.2% acceptance
Feb 25, 2026
650
54
You are given an integer array nums and a positive integer k. A subsequence sub of nums with length x is called valid if it satisfies: (sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k. Return the length of the longest valid subsequence of nums.

Solution

Rust
Time O(n²)
Space O(n)
LeetCode
solution.rs
impl Solution {
  pub fn maximum_length(nums: Vec<i32>, k: i32) -> i32 {
    let k = k as usize;
    let mut ans = 0i32;
    // For each target remainder t, find longest subseq where (a+b)%k == t
    // dp[r] = longest valid subseq ending with element ≡ r (mod k)
    for t in 0..k {
      let mut dp = vec![0i32; k];
      for &x in &nums {
        let r = ((x % k as i32 + k as i32) % k as i32) as usize;
        let prev = (t + k - r) % k;
        dp[r] = dp[prev] + 1;
        if dp[r] > ans {
          ans = dp[r];
        }
      }
    }
    ans
  }
}