Find the Maximum Length of a Good Subsequence I
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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.
Examples
Example 1
Input: nums = [1,2,1,1,3], k = 2
Output: 4
Explanation:
The maximum length subsequence is `[_1_ ,_2_ ,_1_ ,_1_ ,3]`.
Example 2
Input: nums = [1,2,3,4,5,1], k = 0
Output: 2
Explanation:
The maximum length subsequence is `[_1_ ,2,3,4,5,_1_]`.
Constraints
1 <= nums.length <= 5001 <= nums[i] <= 10^90 <= k <= min(nums.length, 25)
Solution
Method 1 – Dynamic Programming (Count Transitions)
Intuition
We want the longest subsequence with at most k transitions (places where adjacent elements differ). This is a classic DP problem: for each position and possible last value, track the best result for a given number of transitions.
Approach
- Use a DP table:
dp[i][t][v]= max length of a good subsequence using firstielements, withttransitions, ending with valuev. - For each number, try to extend all previous subsequences, increasing the transition count if the value changes.
- The answer is the maximum length for any value and at most
ktransitions. - For efficiency, use a dictionary to store only relevant states.
Code
C++
class Solution {
public:
int maximumLength(vector<int>& nums, int k) {
int n = nums.size(), ans = 0;
unordered_map<int, vector<int>> dp; // dp[val][t] = max len ending with val, t transitions
for(int x : nums) {
unordered_map<int, vector<int>> ndp = dp;
for(auto& [v, arr] : dp) {
for(int t=0;t<=k;++t) if(arr[t]) {
int nt = t + (v != x);
if(nt <= k) {
if(ndp[x].size()<=nt) ndp[x].resize(nt+1);
ndp[x][nt] = max(ndp[x][nt], arr[t]+1);
}
}
}
if(ndp[x].empty()) ndp[x]=vector<int>(k+1,0);
ndp[x][0]=max(ndp[x][0],1);
dp = ndp;
}
for(auto& [v, arr] : dp) for(int t=0;t<=k;++t) ans=max(ans,arr[t]);
return ans;
}
};
Go
func maximumLength(nums []int, k int) int {
n, ans := len(nums), 0
dp := map[int][]int{}
for _, x := range nums {
ndp := map[int][]int{}
for v, arr := range dp {
for t, l := range arr {
nt := t
if v != x { nt++ }
if nt <= k {
if len(ndp[x]) <= nt {
tmp := make([]int, nt+1)
copy(tmp, ndp[x])
ndp[x] = tmp
}
if ndp[x][nt] < l+1 {
ndp[x][nt] = l+1
}
}
}
}
if _, ok := ndp[x]; !ok { ndp[x] = make([]int, k+1) }
if ndp[x][0] < 1 { ndp[x][0] = 1 }
dp = ndp
}
for _, arr := range dp {
for _, l := range arr {
if l > ans { ans = l }
}
}
return ans
}
Java
class Solution {
public int maximumLength(int[] nums, int k) {
int n = nums.length, ans = 0;
Map<Integer, int[]> dp = new HashMap<>();
for(int x : nums) {
Map<Integer, int[]> ndp = new HashMap<>();
for(var e : dp.entrySet()) {
int v = e.getKey();
int[] arr = e.getValue();
for(int t=0;t<=k;++t) if(arr[t]>0) {
int nt = t + (v!=x?1:0);
if(nt<=k) {
ndp.putIfAbsent(x, new int[k+1]);
ndp.get(x)[nt] = Math.max(ndp.get(x)[nt], arr[t]+1);
}
}
}
ndp.putIfAbsent(x, new int[k+1]);
ndp.get(x)[0] = Math.max(ndp.get(x)[0], 1);
dp = ndp;
}
for(var arr : dp.values()) for(int l : arr) ans=Math.max(ans,l);
return ans;
}
}
Kotlin
class Solution {
fun maximumLength(nums: IntArray, k: Int): Int {
var dp = mutableMapOf<Int, IntArray>()
for (x in nums) {
val ndp = mutableMapOf<Int, IntArray>()
for ((v, arr) in dp) {
for (t in arr.indices) if (arr[t]>0) {
val nt = t + if (v != x) 1 else 0
if (nt <= k) {
ndp.getOrPut(x) { IntArray(k+1) }
ndp[x]!![nt] = maxOf(ndp[x]!![nt], arr[t]+1)
}
}
}
ndp.getOrPut(x) { IntArray(k+1) }
ndp[x]!![0] = maxOf(ndp[x]!![0], 1)
dp = ndp
}
return dp.values.flatMap { it.asList() }.maxOrNull() ?: 0
}
}
Python
class Solution:
def maximumLength(self, nums: list[int], k: int) -> int:
from collections import defaultdict
dp = defaultdict(lambda: [0]*(k+1))
for x in nums:
ndp = defaultdict(lambda: [0]*(k+1))
for v, arr in dp.items():
for t in range(k+1):
if arr[t]:
nt = t + (v != x)
if nt <= k:
ndp[x][nt] = max(ndp[x][nt], arr[t]+1)
ndp[x][0] = max(ndp[x][0], 1)
dp = ndp
return max(max(arr) for arr in dp.values()) if dp else 0
Rust
use std::collections::HashMap;
impl Solution {
pub fn maximum_length(nums: Vec<i32>, k: i32) -> i32 {
let k = k as usize;
let mut dp: HashMap<i32, Vec<i32>> = HashMap::new();
for &x in &nums {
let mut ndp = HashMap::new();
for (&v, arr) in &dp {
for t in 0..=k {
if arr[t]>0 {
let nt = t + if v!=x {1} else {0};
if nt<=k {
ndp.entry(x).or_insert(vec![0;k+1]);
ndp.get_mut(&x).unwrap()[nt] = ndp.get(&x).unwrap()[nt].max(arr[t]+1);
}
}
}
}
ndp.entry(x).or_insert(vec![0;k+1]);
ndp.get_mut(&x).unwrap()[0] = ndp.get(&x).unwrap()[0].max(1);
dp = ndp;
}
dp.values().flat_map(|arr| arr.iter()).copied().max().unwrap_or(0)
}
}
TypeScript
class Solution {
maximumLength(nums: number[], k: number): number {
let dp = new Map<number, number[]>();
for(const x of nums) {
const ndp = new Map<number, number[]>();
for(const [v, arr] of dp.entries()) {
for(let t=0;t<=k;++t) if(arr[t]) {
const nt = t + (v!==x?1:0);
if(nt<=k) {
if(!ndp.has(x)) ndp.set(x, Array(k+1).fill(0));
ndp.get(x)![nt] = Math.max(ndp.get(x)![nt], arr[t]+1);
}
}
}
if(!ndp.has(x)) ndp.set(x, Array(k+1).fill(0));
ndp.get(x)![0] = Math.max(ndp.get(x)![0], 1);
dp = ndp;
}
let ans = 0;
for(const arr of dp.values()) for(const l of arr) ans = Math.max(ans, l);
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n*k*U), where n is the length of nums and U is the number of unique values in nums. - 🧺 Space complexity:
O(k*U), for the DP table