Leetcode 300. 最长上升子序列(n方dp,nlogn贪心+二分查找）

输入: [10,9,2,5,3,7,101,18]
输出: 4 

解释: 最长的上升子序列是 [2,3,7,101]，
它的长度是 
4

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
//定义 dp[i]dp[i] 为考虑前 ii 个元素，以第 ii 个数字结尾的最长上升子序列的长度，注意 \textit{nums}[i]nums[i] 必须被选取。

    int dp[nums.size()+5];
    for(int i=0;i<nums.size()+5;i++)dp[i]=1;
    int maxx=1;
    int k=nums.size();
    if(!k)return 0;
    for(int i=1;i<k;i++)
    {
        for(int j=i-1;j>=0;j--)
        if(nums[i]>nums[j])dp[i]=max(dp[j]+1,dp[i]),maxx=max(maxx,dp[i]);
    }
    return maxx;
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int k=nums.size();
        if(!k)return 0;
        vector<int>d;
        d.push_back(nums[0]);//表示长度i末尾元素值
        int len=1;
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]>d[len-1])d.push_back(nums[i]),len++;
            else
            {
                *lower_bound(d.begin(),d.end(),nums[i])=nums[i];
            }
        }
        return len;
    }
};