最长不降子序nlogn 原理

问题描述：给出一个序列，找出其最长不降子充

例如：4 1 3 5 6 2 7结果为：1　3　5　6

题解：

数组ID[n] = {4 1 3 5 6 2 7}.

数组F[n]，设j指向ID，i指向F，F[i]表示在长度为j的序列中，最长不降子序长度为i的子序列的最后一个元素的最小值。所以递推公式为：

0<=i<=len(len：为已求出的最长不降子序的长度)

如果ID[j] <= F[i] （即：长度为i的不降子序的最后一个元素有更小的值ID[j]，

则更新F[i]）则F[i] = ID[j]

如果i == len 并且　ID[j] > F[i ] (即：ID[j] 可以叠加到已求出的最长子序列上，成为len = len+1长度的不降子序上)。则F[i +1] = ID[j]

则最后我们的答案就是len

这样很明显我们的程序有两个for循环，分别是i，j(0<=j<=n,0<=i<=len)

这样一个个查找的时间为n*n

由于F[i]表示在长度为j的序列中，最长不降子序长度为i的子序列的最后一个元素的最小值，所以F为递增，可以用二分查找法找出将要刷新的F单元.

二分查找的时间为logn

所以总时间为n*logn

zju一道典型题

http://acm.zju.edu.cn/show_problem.php?pid=1986

输入数据量比较大，一定要用C的输入输出才可以AC

#include <iostream>
#include <stdio.h>
using namespace std;

int ID[40000],F[40000];
int main()
{
int Case,N;
//cin>>Case;
scanf("%d",&Case);
for(int i=0; i<Case; i++){
//cin>>N;
scanf("%d",&N);
int len = 0;
for(int j=0; j<N; j++){
//cin>>ID[j];
scanf("%d",&ID[j]);
//二分查找
int left=0,right=len-1;
int mid = 0;
while(left<=right){
mid = (left + right)/2;
if(ID[j] < F[mid])
right = mid-1;
else
left = mid+1;
}
if(left != len)
F[left] = ID[j];
else
F[len++]=ID[j];
}
//cout<<len<<endl;
printf("%d\n",len);
}
return 0;
}