例子如4，1，6，2，8，5，7，3
8个数，如何求其最长上升子序列呢。
可以用L[i]表示前面子序列长度为i+1(因为length的下标从0开始)尾元素的最小值。
A[i]装的是每个元素的值。
length=1;
初始化L[0]=A[0].
for i=0 to n-1
if|(L[length-1]<A[I])
L[length++]=A[i];//表明最长的子序列的尾元素小于A[I]，那么就可以更新这个尾元素，并且最长子序列长度++
else //说明这个数小于尾元素
for(j=0,1,2,length-1)到length-1是因为L[length-1]就 为目前最长子序列的尾元素
L数组一定为递增顺序，因为添加时候一定比之前的L[length-1]大才能添加新的length
找到第一个大于A[i]的元素，将其L[j]=A[i]后break即可。（仔细想想）这么更新是为了这个长度的尾元素只要最小的那一个，但只能更新一个。
二分的重点：找满足某条件的最大/最小值该怎么二分。
#include<iostream> #include <stdio.h> #include <string.h> #include <set> #include <vector> #include <stdlib.h> #include<direct.h> #include <io.h> #include <direct.h> using namespace std; int L[500]; int A[500]; int main(){ freopen("in.txt","r",stdin); int i,j,k,f1,f2,f3,t1,t2,t3,n,m,T,t; cin >> n; for(i=0;i<n;i++) cin >> A[i]; memset(L,0,sizeof(L)); L[0]=A[0]; int length=1; for(i=1;i<n;i++) if(L[length-1]<A[i]){ L[length++]=A[i]; cout << length <<" " << i<< endl; }else{ int left1,right1,mid1,min1; min1=1e9+7; left1=0;right1=length-1;//从0更新到length-1 while(right1>=left1){ mid1=(right1+left1)/2; if(L[mid1]<=A[i]) left1=mid1+1; else{ right1=mid1-1; min1=min(mid1,min1); } } L[min1]=A[i]; } cout << length << endl; return 0; }