链接：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;
}
};