Pascal最长上升子列问题LIS.ppt

1、最长上升子列问题LIS,最长上升子列问题LIS,问题： 给出一个数列，要求从这个数列中找出一个最长的子列，使得这个子列的元素是严格单调上升的。 输入： 第一行是一个数N，表示数列的长度。第二行是N个数，表示这个数列。其中N=300000。 输出： 输出仅有一个数，最长子列的长度。 样例输入： 6 3 7 2 4 6 8 样例输出： 4,分析:,1.考虑某个位,到达该位的最长上升序列只与其前面位的数字有关而与其后面位无关,即具有子结构性质; 2.设FI表示第I位数字的最长上升子序列长度,则FI值只与当AJAI(JI)对应的子序列有关,容易获得: FI=MAXFJ(AJAI(JI)+1 3.自底向

2、上的方式计算问题的最优值,显然FI的初值为1,以下是对样例的模拟操作分析,设ai为第i个数，fi为到第i个数最长上升子序列的大小，初始时fi=0，f1=1，,procedure main; var i,j,max:integer; begin max:=1; f1:=1; for i:=2 to n do begin for j:=1 to i-1 do求符合条件子列最大值 if (ajfi) then fi:=fj; inc(fi);子列最大值加1 if fimax then max:=fi; end; writeln(max); end;,算法效率：O(n2),注意观察相同上升长度的子序列

3、，如：长度为4的序列：3 5 6 8，3 4 5 7，3 4 5 6，影响后面最长子序列的是3 4 5 6序列。 证明： 因为6是长度为4序列中尾数最小的序列，如果一个数能加入长度为4的其它序列中也必定能加入该序列中。 故相同长度的子序列的有效信息是其序列中尾数最小的数。因此我们如果增加一个数组记录下每种序列结尾最小值，可不可以降低算法的时间复杂度呢？,序列 3 7 5 4 6 8 5 7 6 7 上升长度 1 2 2 2 3 4 3 4 4 5,建立一个数组sk来储存所有长度为j的最长上升子序列的最后一个数字的最小值。即,sk=minaJ( FJ=K,1=J=I)。,对sk能发现什么性质?,

4、sK值是单调上升的!,改进算法: 原算法的弊端是每次需要花O(n)的时间寻找最优子序列. 由于sK值是单调上升 (1)考虑到ai元素时，用二分法在sk中寻找最大的一个k使skaI，让fI=k+1,否则fI保留原值. (2)IF AI SfI THEN 更新SfI=AI 这样，使算法的复杂度下降为O(nlog2n)。,分步变化示例如下:,(1),(2),(3),(4),(5),(6),program LIS; var n,i,max,k,e:integer;n数据长度，e记录已知序列总数，max最优值 num,dp,maxn:array 1.300000 of integer;num记录数据，d

5、p记录序列长度，maxn记录每种序列结尾最小值 function find(x:integer):integer;二分查找，寻找当前值所在的区间 var left,right,mid:integer; begin left:=1;right:=e; mid:=(left+right) div 2; while leftx then right:=mid-1 else left:=mid+1; mid:=(left+right) div 2; end; find:=mid-1; end;,begin assign(input,lis.in); reset(input); assign(output,lis.out); rewrite(output); readln(n); for i:=1 to n do maxni:=30000; for i:=1 to n do read(numi); dp1:=1; maxn1:=num1; e:=1; for i:=2 to n do 动态规划过程 begin k:=find(numi)+1; if k+1dpi then dpi:=k+1; if k+1e then e:=k+1; if numimaxndpi then maxndpi:=num