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 mostk indices i in the range [0, seq.length - 2] such that seq[i] != seq[i + 1].
Return the maximum possible length of a goodsubsequence 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 <= 5 * 103
1 <= nums[i] <= 109
0 <= k <= min(50, nums.length)
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:
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.
Due to the large data range of this problem, the above solution will time out and needs to be optimized.
According to the state transition equation, if $nums[i] = nums[j]$, then we only need to get the maximum value of $f[j][h]$, we can maintain it with an array $mp$ of length $k + 1$. If $nums[i] \neq nums[j]$, we need to record the maximum value of $f[j][h - 1]$ corresponding to $nums[j]$, the maximum value and the second maximum value, we can maintain it with an array $g$ of length $k + 1$.
The time complexity is $O(n \times k)$, and the space complexity is $O(n \times k)$. Where $n$ is the length of the array nums.