最长不下降子序列问题即是求：一数列中某一严格单增的子序列的最长长度.
举例：<span style="color:#ff4中最长不下降的子序列<span style="color:#ff、<span style="color:#ff、<span style="color:#ff.即是最长长度为3.
一、简单的O(N^2)算法
当我们定义问题F(i)为以bi结束的最长不下降序列时，则问题F(I)
有I-1个子问题：F(1), F(2),…, F(I-1)。我们要使F(I)最大，则要找
到一个F(j)(1≤j≤I-1)最大的子问题，且同时满足Bj & Bi，这时F(I)=F(j)max&#43;1;
如果不存在Bj & Bi(1≤j≤I-1),那么i不存在前驱节点,那么F(I)=1;
//用两个数组a[]数组存数num[]数组存这个数对应的最长不下降子序列长度
int longest(int a[],int n)
int num[n];
for(i=0;i&n;i++) //每次循环就确定了前i项中的最长不下降子序列的长度并存放在num[i]中.
for(j=0;j&i;j++)
if(a[j]&a[i]&&num[j]+1&num[i])
找出当前的前去节点 并更新长度.
num[i]=num[j]+1;
int max=0;
for(i=0;i&n;i++)
if(max&num[i])
max=num[i];
二、复杂的O(NlogN)算法
概述：O(NlogN)的算法在于它建立了一个数组(这里假设为f []).那么f[i]表示读到当前数据的时候 &(这个f[]是每读入题目数组的一个元素的时候就更新一次) &长度为i的严&#26684;单增序列中结尾元素的最小&#20540;,用t来表示当前f[]数组的长度,那么当题目数组全部读完后,t的&#20540;就是最长不下降子序列.
具体点来讲：
& & & & & & & & & &设当前的已求出来的长度为t，则判断a[i]和b[k]；
& & & & & & & & & 1.如果a[i]&b[t].即是a[i]大于长度为 t 的序列中的最后一个元素,这样加入a[i]在这个元素可以使当前序列长度加1.t=t&#43;1,然后现在的b[k]=a[i].
& & & & & & & & & 2.如果a[i]=b[i],即是a[i]]等于长度为 t 的序列中的最后一个元素,那么这个元素当前有无都不影响.
& & & & & & & & & 3.如果a[i]&b[k],那么在b[1]……b[k]中找到最大的 j 使得b[j]&a[i],所以a[i]加入长度为j的j序列里面,这个序列的长度加1,那么就可以更新长度为j&#43;1的序列的最后一个元素,即是b[j&#43;1]=a[i].
#include &stdio.h&
int f[40010];
int longest(int a,int l,int r)
//定义二分查找函数
while(l&=r)
m=(l+r)/2;
if(f[m]==a)
//如果出现当前值和查找的值相同那么自然就更新当前的f[]值,也可理解为不用更新
else if(f[m]&a)
//每次返回的都是在f[]中最大的j能够使得f[j]&a[i]的j+1.
int main()
int N,n,a,i,t,k,j;
scanf(&%d&,&N);
while(N--)
scanf(&%d&,&n);
for(i=0;i&n;i++)
scanf(&%d&,&a);
//每次输入一个数就处理一个数
k=longest(a,1,t);
//如果k&=t说明是情况3.
//否则为情况1,表示最大长度可以更新
{t++;f[t]=a;}
printf(&%d\n&,t);
& & & & & & & & & &算法复杂度的分析：
& & & & & & & & 方法一： 因为共有n个元素要进行计算，每次计算又要查找i次(i从1递增到n),那么时间复杂度就是O(N^2).
& & & & & & & & 方法二：由于f[]数组里面的数是单调递增的,那么查找的时候可以不用遍历而用二分查找,这样时间复杂度就为O(NlogN).
本文已收录于以下专栏：
相关文章推荐
为了更好的介绍O(nlogn)算法，我们回顾一下一般的O(n^2)的算法。
令A[i]表示输入第i个元素，d[i]表示从A[1]到A[i]中以A[i]结尾的最长子序列长度。对于任意的0
最长不下降子序列是一个经典的动态规划问题。假如给出这样一个数组int data[] = {1,5,2,7,6};这个数组有4个最长不下降子序列1,2,7和1,2,6,和1,5,7,和1,5,6，都是长...
设有一个正整数的序列：b1,b2,…，bn，对于下标i1＜im，若有bi1≤bi2≤…≤bim
则称存在一个长度为m的不下降序列。
例如，下列数列
7&#160;9&#160; 16&#160;
题目描述&#160;Description
给一个数组a1, a2 ... an，找到最长的不下降子序列ab1b2&=
.. bk，其中b1
输出长度即可。
输入描述&#160;In...
/articles/VRVFZb
多线程分类中写了21篇多线程的文章，21篇文章的内容很多，个人认为，学习，内容越多、越杂的知识，...
动态规划的几个基本概念
想要掌握好动态规划，首先要明白几个概念：阶段、状态、决策、策略、指标函数。
1．&#160;阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的...
详解最长不下降子序列
/content/13/87.shtml
让我们沿用“入门”一节里那道简单题的思路来一步步找到“状态”和“...
ALEJ并不是财迷，但是作为纯洁党的伟大领袖，不挣钱，纯洁的事业怎么能坚持下去！纯洁党现在已经有M(1
ALEJ想知道，通过一次买卖（种类、数量没有限制）后，纯洁党的...
他的最新文章
讲师：AI100
讲师：谢梁
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)&&&&&&&&&&&&&&&&&&
posts - 63,comments - 0,trackbacks - 0
某国为了防御敌国的导弹袭击，发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于等于前一发的高度。某天，雷达捕捉到敌国导弹来袭。由于该系统还在试用阶段，所以只用一套系统，因此有可能不能拦截所有的导弹。
输入第一行输入测试数据组数N（1&=N&=10）接下来一行输入这组测试数据共有多少个导弹m（1&=m&=20）接下来行输入导弹依次飞来的高度，所有高度值均是大于0的正整数。输出输出最多能拦截的导弹数目样例输入
389 207 155 300 299 170 158 65
求给出序列的最长单调递减子序列的长度。AC代码：
//导弹拦截
2 #include&stdio.h&
3 #include&stdlib.h&
4 #include&string.h&
5 using namespace
6 int num[22];//记录测试数据
7 int dp[22];//记录结果
8 int main()
scanf("%d",&n);//n组测试数据
while(n--)
scanf("%d",&m);//每组m个元素
memset(num,0,sizeof(num));//初始化
memset(dp,0,sizeof(dp));
for(int i=1;i&=m;i++)//输入
scanf("%d",&num[i]);
for(int i=1;i&=m;i++)//自底向上进行填写以i为末尾的序列的单调递减子序列的最大长度
int ans=0;
for(int j=0;j&=i;j++)
if(num[i]&num[j]&&ans&dp[j])
ans=dp[j];
dp[i]=ans+1;
int ans=0;//求出最有值
for(int i=1;i&=m;i++)
if(ans&dp[i])
ans=dp[i];
printf("%d\n",ans);
阅读(...) 评论()温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
一个怀揣着梦想的小菜鸟,一个没有任何背景的奋斗者
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(13942)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'最长不下降子序列的O(n^2)算法和O(nlogn)算法',
blogAbstract:'转帖 最长不下降子序列的O(n^2)算法和O(nlogn)算法
最长不下降子序列(LIS:Longest Increasing Subsequence)
//用句通俗的话说，我讲的很通俗易懂~~
问题描述：给出n个数，求出其最长不下降子序列的长度，比如n=5，5个数是{4,6,5,7,3}；其最长下降子序列就是{4,6,7}，长度为3。
一、简单的O（n^2)的算法
&&&&&&&& 很容易想到用动态规划做。设lis[]用于保存第1~i元素元素中最长不下降序列的长度，则lis[i]=max(lis[j])+1,且num[i]&num[j],i&j。然后在lis[]中找到最大的一个值，时间复杂度是O(n^2)。
&&&&&&&& 代码实现：',
blogTag:'',
blogUrl:'blog/static/6',
isPublished:1,
istop:false,
modifyTime:1,
publishTime:6,
permalink:'blog/static/6',
commentCount:2,
mainCommentCount:2,
recommendCount:3,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'一个怀揣着梦想的小菜鸟,一个没有任何背景的奋斗者',
hmcon:'0',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}