Pascal最长公共子序列问题

《Pascal最长公共子序列问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、两个模型最长上升子列问题LIS；最长公共子序列问题；最长上升子列问题LIS问题：给出一个数列，要求从这个数列中找出一个最长的子列，使得这个子列的元素是严格单调上升的。输入：第一行是一个数N，表示数列的长度。第二行是N个数，表示这个数列。其中N<=300000。输出：输出仅有一个数，最长子列的长度。样例输入：6372468样例输出：4分析:1.考虑某个位,到达该位的最长上升序列只与其前面位的数字有关而与其后面位无关,即具有子结构性质;2.设F[I]表示第I位数字的最长上升子序列长度,则F[I]值只与当A[J]

2、f[i])thenf[i]:=f[j];inc(f[i]);{子列最大值加1}iff[i]>maxthenmax:=f[i];

3、end;writeln(max);end;算法效率：O(n^2)注意观察相同上升长度的子序列，如：长度为4的序列：3568，3457，3456，影响后面最长子序列的是3456序列。证明：因为6是长度为4序列中尾数最小的序列，如果一个数能加入长度为4的其它序列中也必定能加入该序列中。故相同长度的子序列的有效信息是其序列中尾数最小的数。因此我们如果增加一个数组记录下每种序列结尾最小值，可不可以降低算法的时间复杂度呢？序列3754685767上升长度1222343445建立一个数组s[k]来储存所有长度为j的最长上升子序列的最后一个数字的最小值。即s[k]=min{a[J](F[J]=K,1<=

4、J<=I)}。对s[k]能发现什么性质?s[K]值是单调上升的!改进算法:原算法的弊端是每次需要花O(n)的时间寻找最优子序列.由于s[K]值是单调上升(1)考虑到a[i]元素时，用二分法在s[k]中寻找最大的一个k使s[k]

5、度，e记录已知序列总数，max最优值}num,dp,maxn:array[1..300000]ofinteger;{num记录数据，dp记录序列长度，maxn记录每种序列结尾最小值}functionfind(x:integer):integer;{二分查找，寻找当前值所在的区间}varleft,right,mid:integer;beginleft:=1;right:=e;mid:=(left+right)div2;whileleft<=rightdobeginifmaxn[mid]>xthenright:=mid-1elseleft:=mid+1;mid:=(left+right)div

6、2;end;find:=mid-1;end;beginassign(input,'lis.in');reset(input);assign(output,'lis.out');rewrite(output);readln(n);fori:=1tondomaxn[i]:=30000;fori:=1tondoread(num[i]);dp[1]:=1;maxn[1]:=num[1];e:=1;fori:=2tondo{动态规划过程}begink:=find(num[i])+1;ifk+1>dp[i]thendp[i]:=k+1;ifk+1>ethene:=k+1;ifnum[i]

7、p[i]]thenmaxn[dp[i]]:=num[i];end;max:=0;fori:=1tondoifmax