Find the maximum length of a good subsequence i

Array Hash Table Dynamic Programming

32.5% acceptance

Feb 24, 2026

167

You are given an integer array nums and a non-negative integer k. A sequence of integers seq is called good if there are at most k indices i in the range [0, seq.length - 2] such that seq[i] != seq[i + 1]. Return the maximum possible length of a good subsequence of nums.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_length(nums: Vec<i32>, k: i32) -> i32 {
    let k = k as usize;
    let n = nums.len();
    // dp[i][j] = max length of good subseq ending at index i with exactly j transitions
    let mut dp = vec![vec![1i32; k + 1]; n];
    let mut ans = 1;
    for i in 1..n {
      for prev in 0..i {
        for j in 0..=k {
          if nums[prev] == nums[i] {
            if dp[prev][j] + 1 > dp[i][j] {
              dp[i][j] = dp[prev][j] + 1;
            }
          } else if j > 0 && dp[prev][j - 1] + 1 > dp[i][j] {
            dp[i][j] = dp[prev][j - 1] + 1;
          }
          if dp[i][j] > ans {
            ans = dp[i][j];
          }
        }
      }
    }
    ans
  }
}