原文地址：http://www.cnblogs.com/kuangbin/archive/2012/03/22/2412725.html
假设要寻找最长上升子序列的序列是a[n]，然后寻找到的递增子序列放入到数组b中。
（1）当遍历到数组a的第一个元素的时候，就将这个元素放入到b数组中，以后遍历到的元素都和已经放入到b数组中的元素进行比较；
（2）如果比b数组中的每个元素都大，则将该元素插入到b数组的最后一个元素，并且b数组的长度要加1；
（3）如果比b数组中最后一个元素小，就要运用二分法进行查找，查找出第一个比该元素大的最小的元素，然后将其替换。
在这个过程中，只重复执行这两步就可以了，最后b数组的长度就是最长的上升子序列长度。例如：如该数列为：
5 9 4 1 3 7 6 7
那么：
5 //加入
5 9 //加入
4 9 //用4代替了5
1 9 //用1代替4
1 3 //用3代替9
1 3 7 //加入
1 3 6 //用6代替7
1 3 6 7 //加入
最后b中元素的个数就是最长递增子序列的大小，即4。
要注意的是最后数组里的元素并不就一定是所求的序列，
例如如果输入 2 5 1
那么最后得到的数组应该是 1 5
而实际上要求的序列是 2 5
//用二分查找的方法找到一个位置，使得num>b[i-1] 并且num<b[i],并用num代替b[i]
int Search(int num,int low,int high)
{
int mid;
while(low<=high)
{
mid=(low+high)/2;
if(num>=b[mid]) low=mid+1;
else high=mid-1;
}
return low;
}
int DP(int n)
{
int i,len,pos;
b[1]=a[1];
len=1;
for(i=2;i<=n;i++)
{
if(a[i]>=b[len])//如果a[i]比b[]数组中最大还大直接插入到后面即可
{
len=len+1;
b[len]=a[i];
}
else//用二分的方法在b[]数组中找出第一个比a[i]大的位置并且让a[i]替代这个位置
{
pos=Search(a[i],1,len);
b[pos]=a[i];
}
}
return len;
}