昨日与今日题目相同，只有数据量变大了

题目

给定一个整数数组 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]。

示例 2：
输入：nums = [1,2,3,4,5,1]，k = 0
输出：2
解释：最长好子序列为 [1,1]

提示：

1. 1 <= nums.length <= 5 * 10^3；
2. 1 <= nums[i] <= 109；
3. 0 <= k <= min(50, nums.length)。

解题思路

见代码

代码

/*
#1 作为第 i 个数，其有三种情况：1.单独作为一个子序列2.和上一个好子序列的最后一个相同，加入到结尾3.和上一个好子序列的最后一个不相同，但是不超过k，加入到结尾#2 所需要的跟踪信息有：子序列的结尾数，相邻不同的个数#3 dp的构造：//1 构造dp[i][j],表示以 nums[i] 作为结尾，至多有 j 个相邻不同的子序列，记录这个下面的最长子序列的长度//2 根据 #1 得出下方：1.作为子序列的第一个数，dp[i][j]+1;2.作为系序列的末尾，并于末尾的数相同，dp[i][j]+1;3.作为子序列的末尾，并于末尾的数相同，dp[i][j]=dp[y][j-1]+1;//y为0~i//3 dp[i][j]的空间大小：i的值为0~n-1，j的值为0~k
#1 优化//dp构造优化：根据 #3 的 //1 可以优化构造的方式，其中前面的dp[i]表示以nums[i]作为结尾，我们可以通过哈希的方式快速构建unordered_map<int,vector<int>> dp;//最大值的维护(对于昨日的I，可以通过暴力枚举y的值而得到，而对于本体暴力枚举则会超时)假设最大值为max_v[j-1],用于记录dp[y][j-1]的最大值,避免多次寻找y的最大值*/
class Solution {
public:int maximumLength(vector<int>& nums, int k) {unordered_map<int,vector<int>> dp;vector<int> max_v(k+2);for(int num:nums){auto& d=dp[num];d.resize(k+1);for(int j=k;j>=0;j--){//正着循环则会导致同一个数被统计多次d[j]=max(d[j],max_v[j])+1;max_v[j+1]=max(max_v[j+1],d[j]);}}return max_v[k+1];}
};