# 3176. Find the Maximum Length of a Good Subsequence I

## Description

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.

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 <= 500
• 1 <= nums[i] <= 109
• 0 <= k <= min(nums.length, 25)

## Solutions

### Solution 1: Dynamic Programming

We define $f[i][h]$ as the length of the longest good subsequence ending with $nums[i]$ and having no more than $h$ indices satisfying the condition. Initially, $f[i][h] = 1$. The answer is $\max(f[i][k])$, where $0 \le i < n$.

We consider how to calculate $f[i][h]$. We can enumerate $0 \le j < i$, if $nums[i] = nums[j]$, then $f[i][h] = \max(f[i][h], f[j][h] + 1)$; otherwise, if $h > 0$, then $f[i][h] = \max(f[i][h], f[j][h - 1] + 1)$. That is:

$f[i][h]= \begin{cases} \max(f[i][h], f[j][h] + 1), & \text{if } nums[i] = nums[j], \\ \max(f[i][h], f[j][h - 1] + 1), & \text{if } h > 0. \end{cases}$

The final answer is $\max(f[i][k])$, where $0 \le i < n$.

The time complexity is $O(n^2 \times k)$, and the space complexity is $O(n \times k)$. Where $n$ is the length of the array nums.

• class Solution {
public int maximumLength(int[] nums, int k) {
int n = nums.length;
int[][] f = new int[n][k + 1];
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int h = 0; h <= k; ++h) {
for (int j = 0; j < i; ++j) {
if (nums[i] == nums[j]) {
f[i][h] = Math.max(f[i][h], f[j][h]);
} else if (h > 0) {
f[i][h] = Math.max(f[i][h], f[j][h - 1]);
}
}
++f[i][h];
}
ans = Math.max(ans, f[i][k]);
}
return ans;
}
}

• class Solution {
public:
int maximumLength(vector<int>& nums, int k) {
int n = nums.size();
int f[n][k + 1];
memset(f, 0, sizeof(f));
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int h = 0; h <= k; ++h) {
for (int j = 0; j < i; ++j) {
if (nums[i] == nums[j]) {
f[i][h] = max(f[i][h], f[j][h]);
} else if (h) {
f[i][h] = max(f[i][h], f[j][h - 1]);
}
}
++f[i][h];
}
ans = max(ans, f[i][k]);
}
return ans;
}
};

• class Solution:
def maximumLength(self, nums: List[int], k: int) -> int:
n = len(nums)
f = [[1] * (k + 1) for _ in range(n)]
ans = 0
for i, x in enumerate(nums):
for h in range(k + 1):
for j, y in enumerate(nums[:i]):
if x == y:
f[i][h] = max(f[i][h], f[j][h] + 1)
elif h:
f[i][h] = max(f[i][h], f[j][h - 1] + 1)
ans = max(ans, f[i][k])
return ans


• func maximumLength(nums []int, k int) (ans int) {
f := make([][]int, len(nums))
for i := range f {
f[i] = make([]int, k+1)
}
for i, x := range nums {
for h := 0; h <= k; h++ {
for j, y := range nums[:i] {
if x == y {
f[i][h] = max(f[i][h], f[j][h])
} else if h > 0 {
f[i][h] = max(f[i][h], f[j][h-1])
}
}
f[i][h]++
}
ans = max(ans, f[i][k])
}
return
}

• function maximumLength(nums: number[], k: number): number {
const n = nums.length;
const f: number[][] = Array.from({ length: n }, () => Array(k + 1).fill(0));
let ans = 0;
for (let i = 0; i < n; ++i) {
for (let h = 0; h <= k; ++h) {
for (let j = 0; j < i; ++j) {
if (nums[i] === nums[j]) {
f[i][h] = Math.max(f[i][h], f[j][h]);
} else if (h) {
f[i][h] = Math.max(f[i][h], f[j][h - 1]);
}
}
++f[i][h];
}
ans = Math.max(ans, f[i][k]);
}
return ans;
}