力扣打卡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;}
};