力扣打卡8：最长上升子序列

链接：300. 最长递增子序列 - 力扣（LeetCode）

本题我开始想到的是dp，复杂度为O(n^2)，这也是很经典的解法。

看到进阶解法可以O(nlogn)，想到可能是要用到二分，但是，我想到的是和map排序，再二分查找第一个比当前值小的数，再找比它小的所有数，中维护max序列，再塞到map中，可惜严格来讲还是O(n^2)。

看完官方题解，才明白要贪心来贪最小的位置，再结合二分查找，维护一条最长最优的序列。

方法一：dp

class Solution {
public:
    int a[2501];
    int lengthOfLIS(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)
        {
            int mx=0;
            for(int j=0;j<i;j++) if(nums[i]>nums[j]&&a[j]>mx) mx=a[j];
            a[i]=mx+1;
        }
        int ans=0;
        for(int i=0;i<nums.size();i++) if(ans<a[i]) ans=a[i];
        return ans;
    }
};

方法二：贪心+二分

class Solution {
public:
    int a[2501];
    int lengthOfLIS(vector<int>& nums) {
        int len=1;
        a[0]=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            int t=nums[i];
            if(t<=a[0])
            {
                a[0]=t;
                continue;
            }
            if(t>a[len-1])
            {
                a[len++]=t;
                continue;
            } 
            int l=0,r=len-1,m=0;
            while(l<r)
            {
                m=l+(r-l)/2;
                if(a[m]>=t) r=m;
                else l=m+1;
            }
            if(a[r]==t) continue;
            a[r]=t;
        }
        return len;
    }
};