`
wunke
  • 浏览: 10352 次
  • 性别: Icon_minigender_1
  • 来自: 广州
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

最长不降子序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;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics