最长单调子序列（DP）-白红宇

最长单调子序列（DP）

阅读量：6681 次

发布时间：2019-06-25

本文共 2024 字，大约阅读时间需要 6 分钟。

问题描述：给定某一组无序的数，求其中最长的单调序列的长度（该单调序列不一定是连续的），如在 5 6 1 2 4 7 5 中最长上升增序列是1 2 4 7 或者1 2 4 5。

该题可以用动态规划的方法解决，时间复杂度为O（n^2）：

设A[t]表示序列中的第t个数，F[t]表示从1到t这一段中以t结尾的最长上升子序列的长度。

动态规划方程：F[t] = max{1, F[j] + 1} ，其中( j = 1, 2, ..., t - 1, 且A[j] =< A[t] )。（注意：这篇文章我们假设是非严格单调上升，如果严格作单调上升则为：A[j] < A[t]，下同）

通过以上公式求得最长上升子序列的长度为max( F(t) )。

printResultSeq函数通过递归的方法来打印出所有的最长子序列。

参考代码：

1 //seq：保存当前已经计算好的序列，(从后往前计算); 2 //len：最长子序列的长度; 3 //tmpresult：当前要求得子序列长度; 4 //end：在F中查找长度为tmpresult的位置，查找范围为[0,end); 5 //A:原始序列; 6 //F :对应正文算法分析中的F; 7 void printResultSeq(int A[],int F[],int end,int tmpresult,int seq[],int len) 8 { 9     for(int i=0;i
     
      =A[j])39                 F[i]=max(F[i], F[j]+1);40         }41         if(result
      
       ::max(); //the max of int 48     printResultSeq(A, F, n, result,seq,result);49 50     return result;51 }

---------------------------------------------------------------------------

下面是改进后的O（nlogn）的算法：

我们仔细考虑计算F[t]时的情况。假设有两个元素A[x]和A[y]，满足

(1)x < y < t

(2)A[x] < A[y] < A[t]

(3)F[x] = F[y]

此时，选择F[x]和选择F[y]都可以得到同样的F[t]值，那么，在最长上升子序列的这个位置中，应该选择A[x]还是应该选择A[y]呢？

很明显，选择A[x]比选择A[y]要好。因为由于条件(2)，在A[x+1] ... A[t-1]这一段中，如果存在A[z]，A[x] < A[z] < a[y]，则与选择A[y]相比，将会得到更长的上升子序列。

从以上的分析中我们得出一个结论：

如果我们知道A[0:t-1]的最长单调上升子序列的长度为 k，以及所有长度为k的上升子序列中结尾元素的最小值（记为b[k]），我们的关键是维护这个数组b[]

那么如果A[t]>=b[k], 则 A[0:t]的最长单调上升子序列的长度为k+1，且b[k+1]=A[t] ; （结论1）

如果A[t]<b[k], 则 A[0:t]的最长单调上升子序列的长度为k：若A[t]<b[1]，则b[1]=A[t]，

若b[1]=< A[t] =<b[k] ，由“结论1”可知数组 b 是有序的，用二分法插之后到下标 j 使得b[j-1]=<A[t]<b[j]，把b[j] 的值变为A[t]

参考代码：

1 int binary(int b[],int k,int key) 2 { 3     if(key
     
      <= key )low=k; 8         else high=k; 9     }10     return high;11 }12 13 int fun2(int A[] ,int n)14 {15     int *b=new int[n+1],k=1;16     b[1]=A[0];17     for(int i=1;i
      
       =b[k])b[++k]=A[i];20         else b[binary(b,k,A[i])]=A[i];21     }22     return k;23 }

对于该算法怎么打印所有结果还没有研究？？？？？？？

还有另一种做法，先对原数组排序得到A1，然后求A和A1的最长公共子序列

可参考编程之美2.16 求数组中最长递增子序列

转载于:https://www.cnblogs.com/TenosDoIt/archive/2013/04/19/3031589.html

你可能感兴趣的文章