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 <= 5 * 10^3
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= min(50, nums.length)

Solution

Method 1 – Dynamic Programming with State Compression

Intuition

We want the longest subsequence with at most k transitions (places where adjacent elements differ). For this hard version, the constraints are larger, so we need to optimize the DP by compressing the state and using hash maps for only relevant states.

Approach

  1. Use a dictionary to store the best result for each (last value, transitions) pair.
  2. For each number in nums, for each existing state, try to extend the subsequence:
    • If the value changes, increment the transition count.
    • Only keep the best length for each (value, transitions) pair.
  3. Always allow starting a new subsequence with the current number and 0 transitions.
  4. The answer is the maximum length for any state with at most k transitions.

Code

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

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        unordered_map<long long, int> dp; // key: (val<<5)|t, value: max len
        int ans = 0;
        for(int x : nums) {
            unordered_map<long long, int> ndp;
            ndp[(long long(x)<<5)] = 1;
            for(auto& [key, l] : dp) {
                int v = key>>5, t = key&31;
                int nt = t + (v!=x);
                if(nt<=k) {
                    long long nk = (long long(x)<<5)|nt;
                    ndp[nk] = max(ndp[nk], l+1);
                }
            }
            for(auto& [key, l] : ndp) ans = max(ans, l);
            dp = move(ndp);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func maximumLength(nums []int, k int) int {
    dp := map[[2]int]int{} // [val, t] -> max len
    ans := 0
    for _, x := range nums {
        ndp := map[[2]int]int{}
        ndp[[2]int{x, 0}] = 1
        for key, l := range dp {
            v, t := key[0], key[1]
            nt := t
            if v != x { nt++ }
            if nt <= k {
                nk := [2]int{x, nt}
                if ndp[nk] < l+1 { ndp[nk] = l+1 }
            }
        }
        for _, l := range ndp {
            if l > ans { ans = l }
        }
        dp = ndp
    }
    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 {
    public int maximumLength(int[] nums, int k) {
        Map<Long, Integer> dp = new HashMap<>();
        int ans = 0;
        for(int x : nums) {
            Map<Long, Integer> ndp = new HashMap<>();
            ndp.put(((long)x<<5), 1);
            for(var e : dp.entrySet()) {
                int v = (int)(e.getKey()>>5), t = (int)(e.getKey()&31);
                int nt = t + (v!=x?1:0);
                if(nt<=k) {
                    long nk = ((long)x<<5)|nt;
                    ndp.put(nk, Math.max(ndp.getOrDefault(nk, 0), e.getValue()+1));
                }
            }
            for(int l : ndp.values()) ans = Math.max(ans, l);
            dp = ndp;
        }
        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<Pair<Int,Int>,Int>()
        var ans = 0
        for (x in nums) {
            val ndp = mutableMapOf<Pair<Int,Int>,Int>()
            ndp[x to 0] = 1
            for ((key, l) in dp) {
                val (v, t) = key
                val nt = t + if (v != x) 1 else 0
                if (nt <= k) {
                    val nk = x to nt
                    ndp[nk] = maxOf(ndp.getOrDefault(nk,0), l+1)
                }
            }
            for (l in ndp.values) ans = maxOf(ans, l)
            dp = ndp
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def maximumLength(self, nums: list[int], k: int) -> int:
        dp = dict()  # (val, t) -> max len
        ans = 0
        for x in nums:
            ndp = dict()
            ndp[(x, 0)] = 1
            for (v, t), l in dp.items():
                nt = t + (v != x)
                if nt <= k:
                    nk = (x, nt)
                    ndp[nk] = max(ndp.get(nk, 0), l+1)
            for l in ndp.values():
                ans = max(ans, l)
            dp = ndp
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

use std::collections::HashMap;
impl Solution {
    pub fn maximum_length(nums: Vec<i32>, k: i32) -> i32 {
        let mut dp = HashMap::new(); // (val, t) -> max len
        let mut ans = 0;
        for &x in &nums {
            let mut ndp = HashMap::new();
            ndp.insert((x, 0), 1);
            for (&(v, t), &l) in &dp {
                let nt = t + if v != x { 1 } else { 0 };
                if nt <= k {
                    let nk = (x, nt);
                    ndp.insert(nk, ndp.get(&nk).copied().unwrap_or(0).max(l+1));
                }
            }
            for &l in ndp.values() { ans = ans.max(l); }
            dp = ndp;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    maximumLength(nums: number[], k: number): number {
        let dp = new Map<string, number>();
        let ans = 0;
        for(const x of nums) {
            const ndp = new Map<string, number>();
            ndp.set(`${x},0`, 1);
            for(const [key, l] of dp.entries()) {
                const [v, t] = key.split(',').map(Number);
                const nt = t + (v!==x?1:0);
                if(nt<=k) {
                    const nk = `${x},${nt}`;
                    ndp.set(nk, Math.max(ndp.get(nk)||0, l+1));
                }
            }
            for(const l of ndp.values()) ans = Math.max(ans, l);
            dp = ndp;
        }
        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