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