LCS

#include<bits/stdc++.h>
using namespace std;
int f[1000006];
int num[1000006];
int n;
int main()
{
	
	int Max=-1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&f[i]);
	for(int i=1;i<=n;i++)
	num[i]=1;
	for(int i=n;i>=1;i--)
	{
		for(int j=i+1;j<=n;j++)
		if(f[j]>f[i]) num[i]=max(num[i],num[j]+1);
		Max=max(Max,num[i]);
	}
	cout<<Max;
 } //O(n^2) 65pts 

#include<bits/stdc++.h>
using namespace std;
int a[1000006];
int g[1000006];
int n;
int find(int l,int r,int num)
{
	while(r-l>1)//这里的二分可以细细琢磨
	{
		int mid=(l+r)/2;
		if(g[mid]>num) r=mid;//有大于的可以保留r，此时较小的num有可能替换掉了原先较大的g[mid]，不能直接mid-1
		else l=mid;//符合时答案保底是mid，但不一定是mid+1
	}
	return r;
}
int main()
{
	int T=0;
	int Max=-1;
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	
	T=1;
	int lg=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>g[lg]) 
		{
			lg++;
			g[lg]=a[i];
		}
		else
		{
			int k=find(0,lg,a[i]);
			g[k]=a[i];
		}
	}	
	cout<<lg;
 } //O(nlogn) 100ptx

#include<bits/stdc++.h>
using namespace std;
int f[1000001],a[1000001],l,k;
int main() 
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f[i]=0x7fffffff;
		//初始值要设为INF
		/*原因很简单，每遇到一个新的元素时，就跟已经记录的f数组当前所记录的最长
		上升子序列的末尾元素相比较：如果小于此元素，那么就不断向前找，直到找到
		一个刚好比它大的元素，替换；反之如果大于，么填到末尾元素的下一个q，INF
                就是为了方便向后替换啊！*/ 
	}
	f[1]=a[1];
	int len=1;//通过记录f数组的有效位数，求得个数 
	/*因为上文中所提到我们有可能要不断向前寻找，
	所以可以采用二分查找的策略，这便是将时间复杂
    度降成nlogn级别的关键因素。*/ 
	for(int i=2;i<=n;i++)
	{
		int l=0,r=len,mid;
		if(a[i]>f[len])f[++len]=a[i];
		//如果刚好大于末尾，暂时向后顺次填充 
		else 
		{
		while(l<r)
		{	
		    mid=(l+r)/2;
		    if(f[mid]>a[i])r=mid;
	//如果仍然小于之前所记录的最小末尾，那么不断
	//向前寻找(因为是最长上升子序列，所以f数组必
	//然满足单调) 
			else l=mid+1; 
		}
		f[l]=min(a[i],f[l]);//更新最小末尾 
     	}
    }
    cout<<len;
    return 0;
}

将原来的dp数组的存储由数值换成该序列中，上升子序列长度为i的上升子序列，的最小末尾数值

这其实就是一种几近贪心的思想：我们当前的上升子序列长度如果已经确定，那么如果这种长度的子序列的结尾元素越小，后面的元素就可以更方便地加入到这条我们臆测的、可作为结果、的上升子序列中。