#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)
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
}
}