3177. 求出最长好子序列 II / 3176. 求出最长好子序列 I（24.9.7 / 24.9.8）

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

题目

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