求出最长好子序列

给你一个整数数组 nums 和一个 非负 整数 k 。
如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为好序列。
请你返回 nums 中好子序列的最长长度

1. 动态规划

dp[i][j]表示将把i作为序列最后放进去，不超过j个不符合要求的最长好序列长度
这里需要三重循环，因为每次还要遍历前面的进行判断和转移

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
         //小于等于k个，不等，相等不计数
        int n = nums.size();
        //dp[i][j]表示将把i作为序列最后放进去，不超过j个不符合要求的最长好序列长度
        vector<vector<int>> dp(n+1,vector<int>(k+1,1));
        int res = 1;
        for(int i=1;i<n;i++){//遍历数组每一个数，作为序列结尾
            for(int j=0;j<i;j++){//根据前面情况进行转移
                //如果相同，则不占据指标，不同则需要占据一个指标
                if(nums[i]==nums[j]){
                    for(int l=0;l<=k;l++)
                        dp[i][l] = max(dp[i][l],dp[j][l]+1);//序列长度增加
                }
                else{
                    for(int l=1;l<=k;l++)
                        dp[i][l] = max(dp[i][l],dp[j][l-1]+1);//序列长度增加
                }
            }
            res = max(res,dp[i][k]);
        }
        return res;
    }
};

2. 动态规划优化

缩减为两重循环，将逐个与前面序列判断去掉，直接转移，需要记录相同值的最大值，和不同值的最大值

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        unordered_map<int, vector<int>> fs;
        vector<int> mx(k + 2);
        for (int x : nums) {
            auto& f = fs[x];//对应相同值x的数组
            f.resize(k + 1);//初始化
            for (int j = k; j >= 0; j--) {
                f[j] = max(f[j], mx[j]) + 1;
                mx[j + 1] = max(mx[j + 1], f[j]);
            }
        }
        return mx[k + 1];
    }
};