This blog post is only available in Simplified Chinse.
最长上升子序列，全称Longest Increasing Sequence，简称LIS，在计算机科学上是指一个序列中最长的单调递增的子序列（百度百科）。这个序列不一定是连续的。
之前说过，动态规划就是把一个问题分成一大堆子问题，对这些子问题求解，最后求解出这个问题。如何求最长升序列？我们可以想到，随便取一个数字a[i]（当然是在序列里），要是我们知道a[i]之前的且最后一个数据比a[i]小的最长上升子序列长度该多好！直接+1就是以i为结尾的最长上升子序列长度。那么要知道之前的最长升序列长度，就要按照同样的方法找之前的之前……显然是动态规划。
一、普通的DP方法
定义F[i]表示以队列中第i个元素（a[i]）为结尾（其中第i个元素必取）的最长上升子序列长度。转移方程：F[i]=max(F[i],F[j]+1); (a[i]>a[j] && i>j)这样求时间复杂度O（N²）。
二、二分优化的方法
另一种求法是二分优化。维护一个单调不降的序列que，同样定义F[i]为以队列中第i个元素（a[i]）为结尾（其中第i个元素必取）的最长上升子序列长度。有个贪心的想法：我们要让最长上升子序列尽量长，就要让序列中最后一个元素尽量小（这样才能让后面元素可以加入的可能性更大），所以对于每个数字a[i]，在序列中用二分找一个大于a[i]且最接近a[i]的数字替换，这样并不会影响序列的长度，也能保证解最优。如果序列里所有数字都小于a[i]就将其加入序列尾部。这里有个问题：替换了序列中的元素，似乎并不能保证替换位置之后的元素在原序列a[i]之后出现？举个栗子：
维护的序列（que数组）：1 3 5 7 9
原序列（a数组）：1 3 5 7 9 4 10（i=6，即现在要处理4这个数字）
本次替换后：1 3 4 7 9
很显然，原序列里1 3 4 7 9并不符合要求（没按照顺序来）。我们接着往下看：下一步，处理6，替换了7，序列变成了1 3 4 7 9 10，长度是6，正确答案是1 3 5 7 9 10，长度也是6，和答案一样！
其实替换不会减小序列长度，只会增加序列长度；如果之前把序列中某个元素替换成a[i]，那么之后新加入序列的元素（非替换）肯定都在a[i]之后！que序列并不是真正的最长上升序列，但是长度一定与真正的最长上升序列相等！这么优化可以把时间复杂度优化到O（Nlog2（N））。
代码（新鲜出炉的！！！）：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=100005;
int n,a[maxn],que[maxn],len=0;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline int find(int x){
int L=1,R=len;
while (L<=R){
int mid=((R-L)>>1)+L;
if (que[mid-1]<x&&x<que[mid]) return mid; else
if (x<que[mid]) R=mid-1; else
L=mid+1;
}
return 0;
}
int main(){
n=read();
for (int i=1;i<=n;i++){
a[i]=read();
int fd=find(a[i]);
if (fd==0) que[++len]=a[i]; else que[fd]=a[i];
}
printf("%d\n",len);
return 0;
}