LIS长度的求解方法
（一）动态规划法
状态设计：F[i]代表以A[i]结尾的LIS的长度
状态转移：F[i]=max{F[j]+1}(1<=j< i,A[j]< A[i])
边界处理：F[i]=1(1<=i<=n)
时间复杂度：O(n^2)
#include<bits/stdc++.h>
using namespace std;
int a[10010];
int dp[10010];
int main()
{
int n;
while(cin>>n&&n)
{
for(int i=0;i<n;i++)
{
cin>>a[i];
dp[i]=1;
}
int ans=0;
for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(a[j]<a[i])
{
dp[i]=max(dp[j]+1,dp[i]);
}
}
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}
return 0;
}（二）贪心+二分法
新建一个low数组，low[i]表示长度为i的LIS结尾元素的最小值。对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。因此，我们只需要维护low数组，对于每一个a[i]，如果a[i] > low[当前最长的LIS长度]，就把a[i]接到当前最长的LIS后面，即low[++当前最长的LIS长度]=a[i]。
那么，怎么维护low数组呢？
对于每一个a[i]，如果a[i]能接到LIS后面，就接上去；否则，就用a[i]取更新low数组。具体方法是，在low数组中找到第一个大于等于a[i]的元素low[j]，用a[i]去更新low[j]。如果从头到尾扫一遍low数组的话，时间复杂度仍是O(n^2)。我们注意到low数组内部一定是单调不降的，所有我们可以二分low数组，找出第一个大于等于a[i]的元素。二分一次low数组的时间复杂度的O(lgn)，所以总的时间复杂度是O(nlogn)。
HDU1257
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f;
using namespace std;
int dp[10010];
int a[10010];
int main()
{
int n;
while(cin>>n&&n)
{
for(int i=0;i<n;i++)
{
cin>>a[i];
dp[i]=INF;
}
for(int i=0;i<n;i++)
{
*lower_bound(dp,dp+n,a[i])=a[i];//找到>=a[i]的第一个元素，并用a[i]替换
}
cout<<lower_bound(dp,dp+n,INF)-dp<<endl;
}
return 0;
}
Upper_bound()和Lower_bound()的用法
（三）树状数组维护
我们再来回顾O(n^2)DP的状态转移方程：F[i]=max{F[j]+1}(1<=j< i,A[j]< A[i])
我们在递推F数组的时候，每次都要把F数组扫一遍求F[j]的最大值，时间开销比较大。我们可以借助数据结构来优化这个过程。用树状数组来维护F数组（据说分块也是可以的，但是分块是O(n*sqrt(n)）的时间复杂度，不如树状数组跑得快），首先把A数组从小到大排序，同时把A[i]在排序之前的序号记录下来。然后从小到大枚举A[i]，每次用编号小于等于A[i]编号的元素的LIS长度+1来更新答案，同时把编号小于等于A[i]编号元素的LIS长度+1。因为A数组已经是有序的，所以可以直接更新。有点绕，具体看代码。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn =103,INF=0x7f7f7f7f;
struct Node{
int val,num;
}z[maxn];
int T[maxn];
int n;
bool cmp(Node a,Node b)
{
return a.val==b.val?a.num<b.num:a.val<b.val;
}
void modify(int x,int y)//把val[x]替换为val[x]和y中较大的数
{
for(;x<=n;x+=x&(-x)) T[x]=max(T[x],y);
}
int query(int x)//返回val[1]~val[x]中的最大值
{
int res=-INF;
for(;x;x-=x&(-x)) res=max(res,T[x]);
return res;
}
int main()
{
int ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&z[i].val);
z[i].num=i;//记住val[i]的编号，有点类似于离散化的处理，但没有去重
}
sort(z+1,z+n+1,cmp);//以权值为第一关键字从小到大排序
for(int i=1;i<=n;i++)//按权值从小到大枚举
{
int maxx=query(z[i].num);//查询编号小于等于num[i]的LIS最大长度
modify(z[i].num,++maxx);//把长度+1，再去更新前面的LIS长度
ans=max(ans,maxx);//更新答案
}
printf("%d
",ans);
return 0;
}