一个数组p[],长度plen,求其中最长单调递增子序列。
定义数组up[]，up[i]表示长度为i的单调递增子序列中最后一位元素最小为up[i]。定义uplen表示最长的子序列长度
up[]必然是单调递增的
证明:
若对于0<i<i+1<=uplen,有up[i]>up[i+1]，那么对于长度为i+1的子序列，只要去掉其中任意一个元素，就可以得到长度为i的子序列并且该子序列最后一位元素小于up[i]，与up[i]定义矛盾。
若对于0<i<i+1<=uplen,有up[i]==up[i+1],那么只需把长度i+1的递增序列，去除最后一个，就可以得到末尾元素更小的长i的子序列，矛盾。
得证。
我们在从前往后的遍历p[]的过程中不断更新up[]数组。
for(int i=0;i<plen;i++)
{
若uplen==0//此时up[]中还没有数据,p[i]是第一个数据，所以最长子序列长度为1，末尾元素p[i]
{
up[1]=p[i];
uplen=1;
}
否则若存在up[index]==p[i]
｛
不做任何更新//或者做一下up[index]=p[i]的操作，这样操作的作用下面可以看到
｝
否则若up[]中存在up[index]使得up[index]<p[i]并且up[index+1]>p[i]//这也就意味着存在一个长度为index的序列，末尾元素小于p[i]，但是长度index+1的序列，末尾元素大于p[i]，这时候我们只需要将p[i]加入到长度为index序列末尾，就可以得到一个长度index+1新的序列，该序列末尾元素小于up[index+1]
｛
up[index+1]=p[i];
｝
否则p[i]是up[]中最小的或者最大的
｛
若p[i]是最小的 up[1]=p[i];//长度为1的子序列就是p[i]
否则 p[i]是最大的，up[uplen+1]=p[i];uplen++;//把p[i]放在最长子序列的末尾，就得到了一个更加长的。
｝
}
我们需要定义一个函数bsearch()用于搜索p[i]在up[]中的位置,然后返回应当更新up[]中的哪一个数据。
有了这个函数就可以把代码改成
for(int i=0;i<plen;i++)
{
int index=bsearch();
up[index]=p[i];//更新up[]
uplen=uplen>index?uplen:index;//更新uplen
}
那么bsearch的根据上面的介绍，该函数具体功能是
1.当存在up[index]==p[i]时，返回index,这样up[index]=p[i]对应的操作就是不更新
2.当p[i]是up[]中最小的时,返回1
3.当p[i]是up[]中最大的时候,返回uplen+1
4当存在up[index]<p[i]&&up[index+1]>p[i]时，返回index+1
5当uplen=0时，返回1
int bsearch(int up[],int uplen,int pi) { int l=1; int r=uplen; while(l<=r) { int mid=(l+r)/2; if(up[mid]>v) r=mid-1; else if(up[mid]<v) l=mid+1; else return mid;//如果pi存在于up[]中，返回其下标 }
return l;
//如果pi是up[]中最小的,那么l会一直等于1，return l即可
//如果pi是up[]中最大的,那么r会一直等于uplen,l会一直增加，直至增加至l==r+1==uplen+1,所以只需要return l;
//如果存在up[index]<p[i]&&up[index+1]>p[i]
//当uplen!=0时，有两种情况会导致r<l。
//1，当l==mid的时候,up[mid]>pi,那么r=l-1。由于up[l]左侧的数据都是确定小于pi的，所以up[r]<up[mid]，又因为up[l]=up[mid]>pi,所以r就是index,而l就是我们要找的index+1。
//2，当l==mid==r的时候up[mid]<pi,那么l=r+1。由于up[r]右侧数据均大于pi，所以up[l]>up[mid],又因为up[r]=up[mid]<pi，所以l就是我们要找的index+1。
//所以return l;
//如果uplen=0,返回1。 }
整个代码如下
#include <iostream> using namespace std; int bsearch(int up[],int uplen,int pi) { int l=1; int r=uplen; while(l<=r) { int mid=(l+r)/2; if(up[mid]>pi) r=mid-1; else if(up[mid]<pi) l=mid+1; else return mid; } return l; } int main() { int p[]={1,9,4,3,5,2,7,6,8}; int up[10]; up[0]=-1; int plen=9; int uplen=0; for(int i=0;i<plen;i++) { int index=bsearch(up,uplen,p[i]); up[index]=p[i]; uplen=uplen>index?uplen:index; } for(int i=1;i<=uplen;i++) cout<<up[i]<<' '; cout<<endl<<uplen<<endl; return 0; }
