题目：
给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。请你返回 nums 中 好 子序列的最长长度
示例 1：
输入：nums = [1,2,1,1,3], k = 2
输出：4
解释：
最长好子序列为 [1,2,1,1,3] 。
示例 2：
输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：
最长好子序列为 [1,2,3,4,5,1] 。
提示：
1 <= nums.length <= 50001 <= nums[i] <= 10^90 <= k <= min(nums.length, 50)
思路：
动态规划困难题：直接上题解
我们可以想到用 dp[i][j] 来表示以 nums[i] 结尾，其中有 j 个数字与其在序列中的后一个数字不相等的最长合法序列的长度。其中 i 的取值小于 n（n 表示 nums 的长度），j 不超过 k。初始时，有 dp[i][0] = 1。在转移时，可以枚举每一个满足 x < i 的下标，有：
dp[i][j] = max(
dp[x][j - 1] + 1 if nums[x] != nums[i]
dp[x][j] + 1 if nums[x] == nums[i]
)
但这样的时间复杂度是 O(n^2 * k)，在此题是不可接受的。实际上，我们只需要枚举两种情况：
nums[i] ！= nums[x]，对于此情况，可以维护一个长度为 k 的辅助数组 zd。其中 zd[j] 表示枚举到位置 i 之前，有 j 个数字与其在序列中的后一个不相等的最长合法序列的长度，那么可以直接写出转移 dp[i][j] = zd[j − 1] + 1。
nums[i] = nums[x]，假设有下标 a < b < c，并且 nums[a] = nums[b] = nums[c]，对于 c 来说如果选取由 a 转移过来计算答案，那么一定不如 a → b → c 更优，所以会选取下标最近的相同的数进行转移。针对这种情况，dp 使用哈希表维护能节省一些空间，并且在哈希表中用 nums[i] 替换 i。
在每一次遍历 i 计算完后更新 zd，最后的 zd[k] 就是答案。
代码：
class Solution {
public:
int maximumLength(vector<int>& nums, int k) {
int len = nums.size();
unordered_map<int, vector<int>> dp;
vector<int> zd(k + 1, 0);
for (int i = 0; i < len; i++) {
int v = nums[i];
if (!dp.count(v)) {
dp[v] = vector<int>(k + 1, 0);
}
auto& tmp = dp[v];
for (int j = 0; j <= k; j++) {
++tmp[j];
if (j > 0) {
tmp[j] = max(tmp[j], zd[j - 1] + 1);
}
}
for (int j = 0; j <= k; j++) {
zd[j] = max(zd[j], tmp[j]);
}
}
return zd[k];
}
};