【算法挨揍日记】day31——673. 最长递增子序列的个数、646. 最长数对链

 673. 最长递增子序列的个数

673. 最长递增子序列的个数

题目解析：

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

解题思路：

 解题代码：

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int>dp(n,1);
        vector<int>f(n,1);
        int retlength=1;
        int retcount=1;
        for(int i=1;i<n;i++)
        {
            //int length=f[0];//0到i-1区间内的最大长度
            for(int j=0;j<i;j++)
            {
                if(nums[j]<nums[i])
                {       
                    if(f[j]+1==f[i])dp[i]+=dp[j];
                    else if(f[j]+1>f[i])
                    {
                        dp[i]=dp[j];
                        f[i]=f[j]+1;
                    }
                }  
            }
            if(retlength==f[i])retcount+=dp[i];
                else if(retlength<f[i])
                {
                    retcount=dp[i];
                    retlength=f[i];
                }
        }
       
        return retcount; 
    }
};

646. 最长数对链

​​​​​​646. 最长数对链

题目描述：

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。

现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。

找出并返回能够形成的 最长数对链的长度 。

你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

解题思路：

解题代码：

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(),pairs.end());
        int n=pairs.size();
        vector<int>dp(n,1);
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(pairs[j][1]<pairs[i][0])
                    dp[i]=max(dp[i],dp[j]+1);
            }
        }
        int ret=1;
        for(int i=0;i<n;i++)
            ret=max(ret,dp[i]);
        return ret;
    }
};