Longest subsequence with at most k value changes

You get an integer array elements and a non-negative integer k.

Choose a subsequence of elements: delete any number of items (possibly none) and keep the rest in their original order. A change is a pair of neighbours in the chosen subsequence whose values differ. For a subsequence s of length m, the number of changes is the count of i with 0 <= i < m - 1 and s[i] != s[i + 1].

Return the maximum length of a subsequence that has at most k changes.

def max_length(elements: list[int], k: int) -> int: ...

Constraints

• 0 <= len(elements) <= 5000
• -10^9 <= elements[i] <= 10^9
• 0 <= k <= 50

Example 1

elements = [3, 8, 3, 8, 3], k = 0
output   = 3

With no changes allowed, every kept value must be the same. Keeping the three 3s gives length 3. Note that a subsequence may skip items, so the answer is not limited to one contiguous run.

Example 2

elements = [6, 6, 2, 2, 6, 5], k = 1
output   = 4

[6, 6, 2, 2] has one change (6 to 2). So does [6, 6, 6, 5]. No subsequence of length 5 has at most one change.