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

1
2
3
4
5
6
7
8


Input: nums = [1,2,1,1,3], k = 2

Output: 4

Explanation:

The maximum length subsequence is `[_1_ ,_2_ ,_1_ ,_1_ ,3]`.

Example 2

1
2
3
4
5
6
7
8


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 <= 500
  • 1 <= nums[i] <= 10^9
  • 0 <= 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

  1. Use a DP table: dp[i][t][v] = max length of a good subsequence using first i elements, with t transitions, ending with value v.
  2. For each number, try to extend all previous subsequences, increasing the transition count if the value changes.
  3. The answer is the maximum length for any value and at most k transitions.
  4. For efficiency, use a dictionary to store only relevant states.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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