Find the maximum length of a good subsequence ii

Array Hash Table Dynamic Programming

25.1% acceptance

Feb 24, 2026

141

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²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_length(nums: Vec<i32>, k: i32) -> i32 {
    let k = k as usize;
    use std::collections::HashMap;
    // dp[val][j] = max length of good subseq ending with value val and exactly j transitions
    let mut dp: HashMap<i32, Vec<i32>> = HashMap::new();
    // max1[j], max2[j]: best and second best over all values for dp[*][j]
    let mut max1 = vec![0i32; k + 1];
    let mut max2 = vec![0i32; k + 1];
    let mut max1_val: Vec<i32> = vec![-1i32; k + 1];
    let mut ans = 1i32;

    for &x in &nums {
      let old_dp = dp.get(&x).cloned().unwrap_or_else(|| vec![0i32; k + 1]);
      let mut new_dp = vec![1i32; k + 1];

      for j in 0..=k {
        // Extend with same value
        new_dp[j] = new_dp[j].max(old_dp[j] + 1);
        // Extend with different value (new transition)
        if j > 0 {
          let best_other = if max1_val[j - 1] == x { max2[j - 1] } else { max1[j - 1] };
          new_dp[j] = new_dp[j].max(best_other + 1);
        }
        if new_dp[j] > ans {
          ans = new_dp[j];
        }
      }

      // Update global max1/max2 after computing all j for this element
      for j in 0..=k {
        if max1_val[j] == x {
          max1[j] = new_dp[j]; // x is the current max, update
        } else if new_dp[j] >= max1[j] {
          max2[j] = max1[j];
          max1[j] = new_dp[j];
          max1_val[j] = x;
        } else if new_dp[j] > max2[j] {
          max2[j] = new_dp[j];
        }
      }
      dp.insert(x, new_dp);
    }
    ans
  }
}