单调递增子序列详解及实现(nlogn).doc

最长不下降子序列的O(n*logn)算法分析如下：设 At表示序列中的第t个数，Ft表示从1到t这一段中以t结尾的最长上升子序列的长度，初始时设F t = 0(t = 1, 2, ., len(A)。则有动态规划方程：Ft = max1, Fj + 1 (j = 1, 2, ., t - 1, 且Aj At)。 现在，我们仔细考虑计算Ft时的情况。假设有两个元素Ax和Ay，满足 (1)x y t (2)Ax Ay At (3)Fx = Fy 此时，选择Fx和选择Fy都可以得到同样的Ft值，那么，在最长上升子序列的这个位置中，应该选择Ax还是应该选择Ay呢？ 很明显，选择Ax比选择Ay要好。因为由于条件(2)，在Ax+1 . At-1这一段中，如果存在Az，Ax Az ay，则与选择Ay相比，将会得到更长的上升子序列。 再根据条件(3)，我们会得到一个启示：根据F的值进行分类。对于F的每一个取值k，我们只需要保留满足Ft = k的所有At中的最小值。设Dk记录这个值，即Dk = minAt (Ft = k)。 注意到D的两个特点： (1)Dk的值是在整个计算过程中是单调不上升的。 (2)D的值是有序的，即D1 D2 D3 . Dlen，则将At接在Dlen后将得到一个更长的上升子序列，len = len + 1， Dlen = A t；否则，在D1.Dlen中，找到最大的j，满足Dj At。令k = j + 1，则有A t = Dk，将At接在Dj后将得到一个更长的上升子序列，更新Dk = At。最后，len即为所要求的最长上 升子序列的长度。 在 上述算法中，若使用朴素的顺序查找在D1.Dlen查找，由于共有O(n)个元素需要计算，每次计算时的复杂度是O(n)，则整个算法的 时间复杂度为O(n2)，与原来的算法相比没有任何进步。但是由于D的特点(2)，我们在D中查找时，可以使用二分查找高效地完成，则整个算法 的时间复杂度下降为O(nlogn)，有了非常显著的提高。需要注意的是，D在算法结束后记录的并不是一个符合题意的最长上升子序列！ #include using namespace std; int find(int *a,int len,int n)/若返回值为x,则ax=nax-1 int left=0,right=len,mid=(left+right)/2; while(leftamid) left=mid+1; else if(namid) right=mid-1; else return mid; mid=(left+right)/2; return left; void fill(int *a,int n) for(int i=0;in) fill(c,n+1); for(i=0;iai; c0=-1;/ 1 c1=a0;/ 2 b0=1;/ 3 for(i=1;in;i+)/ 4 j=find(c,n+1,ai);/ 5 cj=ai;/ 6 bi=j;/7 for(max=i=0;imax) max=bi; coutmaxcj=aicj-1,所以把cj的值更新为ai后，cj+1cjcj-1的性质仍然成 立，即c仍然是单调递增的； 2、循环中，c的值只在第6行发生变化，由cj=ai可知，cj更新为ai后，cj的值只会变 小不会变大，因为进入循环前cj的值是最小的，则循环中把cj更新为更小的ai，当 然此时cj的值仍是最小的; 3、循环中，bi的值在第7行发生了变化，因为有loop invariant的性质2，find函数返回值 为j有：cj-1ai=cj,这说明cj-1是小于ai的，且以cj-1结尾的递增子序列有最大的 长度，即为j-1,把ai接在cj-1后可得到以ai结尾的最长递增子序列，长度为(j-1)+1=j;termination: 循环完后，i=n-1,b0,b1,.,bn-1的值均已求出，即以a0,a1,.,an-1结尾的最长递 增子序列的长度均已求出，再通过第8行的循环，即求出了整个数组的最长递增子序列。 仔细分析上面的代码可以发现，每次循环结束后，假设已经求出c1,c2,c3,.,clen的值，则此时最长递增子序列的长度为len,因此可以把上面的代码更加简化，即可以不需要数组b来辅助存储，第8行的循环也可以省略。 #include using namespace std; int find(int *a,int len,int n)/修改后的二分查找，若返回值为x，则ax=n int left=0,right=len,mid=(left+right)/2; while(leftamid) left=mid+1; else if(nn) for(i=0;iai; b0=1; c0=-1; c1=a0; len=1;/此