注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

最长递增子序列O(nlogn)  

2013-04-03 14:59:59|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
最长递增子序列最直观的做法是dp,即通过递归dp[i]=max{1, dp[j]+1}, j<i and val[j]<val[i],其中dp[i]表示以第i个元素结尾的最长递增子序列的长度。具体关于递增子序列的描述可参见poj2533,以下代码也已求解该题为目标。
按照上述递归方程,从dp[0]求解到dp[n-1]的非递归实现如下所示:

#include<iostream>
#define MAX 1010
using namespace std;
int len[MAX];
int val[MAX];
int main(){
int n, rs=1;
cin>>n;
for(int i=0; i<n; ++i){
cin>>val[i];
len[i]=1;
for(int j=0; j<i; j++){
if(val[j]<val[i] && len[i]<len[j]+1)
len[i] = len[j]+1;
}
if(rs<len[i]) rs=len[i];
}
cout<<rs<<endl;
return 0;
}

上述实现的时间复杂度为O(n^2),主要是因为在求解dp[i]时,需要遍历所有的dp[0]~dp[i-1]。而这也是优化的关键点,即如何减少每次对前面i项的遍历。试想一下,如果某个val[j]<val[i],使得dp[i]更新为dp[j]+1,那么所有小于dp[j]的项其实无需再考虑。根据这个想法,我们可以根据子序列的长度二分前面的i项。但是还有一个问题,如何处理子序列长度相同的那些项。一种方法是把它们都保存下来,当二分到该长度时,找到第一个末尾数小于val[i]的项或找不到为止。这种方法在最坏的情况下与dp无异,且实现起来徒增麻烦。第二种方法则是对于长度相同的项,只记录下末尾数最小的项,因为如果这一项都无法满足小于val[i],其他项就更不可能满足这个条件。根据第二种方法,我们只需要建立一个len数组,其中len[k]表示当前长度为k的递增子序列最小的末尾数是len[k]。考虑第i项时,只需二分len数组已存在的下标范围,找到满足len[k]<val[i]且k最大的位置,并用val[i]更新len[k+1],如果len[k+1]在更新前没赋值过,就将len数组的最大下标增一,最后的结果就是len数组的最大下标。实现代码如下:

#include<iostream>
#include<vector>
#define MAX 1010
using namespace std;
vector<int> len;

// 这里我返回的满足len[k]>=val[i]且k最小的位置

// 和上文红色部分的描述是等价的,只是变成了更新len[k],而不是len[k+1]
int bisearch(int val){
int left=0, right=len.size()-1;
while(left<=right){
int mid = (left+right)>>1;
if(len[mid] < val) left = mid+1;
else right = mid-1;
}
return left;
}

int main(){
int n, val;
cin>>n;
for(int i=0; i<n; ++i){
cin>>val;
int k = bisearch(val);
if(len.size()<=k) len.push_back(val);
else len[k] = val;
}
cout<<len.size()<<endl;
return 0;
}

  评论这张
 
阅读(4366)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017