《【速度快】最长不下子序-陈启峰》由会员分享，可在线阅读，更多相关《【速度快】最长不下子序-陈启峰（2页珍藏版）》请在金锄头文库上搜索。
1、16:05 2007-6-12 求最长不下子序的算法（陈启峰）- -推荐我自创的求最长不下子序的算法算法时间复杂度：O(nlog n) 一般比这个数字小得多算法空间复杂度：O(n)编程序复杂度：较易数据结构：栈算法：1、建立一个栈 stack，清空。stacki表示当前状态下，所有长度为 i 的子序中最后一个数 的最小值。2、按先后顺序循环序列的每一个数，用操作 3 修改当前状态3、如果这个数不小栈顶或栈为空就 i这个数.将 stacki更新为这个数。可以用二分法是因为 stack 是有序的4、输出 stack 的长度。最长不下子序长度优点：这个算法无论是算法时间复杂度，算法空间复杂度或编程序
2、复杂度都十分优秀。补充：如果要求最长不下子序，就只要再建立一个数组 f，在运行完操作 3 后记录每一个 数在子序中是如何得到,即 f这个数的序号-stacki-1的序号.program p1986(input,output); var x:array0.40000 of word;temp,i,c,m,n,k:word; function h(a,b:word):word; beginif a=b then beginh:=a;exit;end;temp:=(a+b)div 2;if xtempxm then begininc(m);xm:=k;endelsexh(1,m):=k;end;writeln(m);end; end.
