最长递减子序列
1、面试题目 求一个数组的最长递减子序列比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5， 4，3，2}
2、解题方法 采用动态规划解决题目
?最长公共子序列方法解决
?直接根据动态转移方程解决
2.1最长公共子序列方法
2.1.1原理
设原来数组为X[1..n]，而数组Y[1…n]为数组X[]的非递增序列，现在我们求X[1…n],Y[1…n]的最长公共子序列，现在简要说下最长公共子序列的原理（详解见算法导论第2版Page208）：
假设序列X={x1, x2, …, xn}和Y ={y1, y2, …,yn}的最长公共子序列为Z = {z1, z2,.., zk}
1)如果xm = yn, 则zk = xm =yn,且zk-1是xm-1与yn-1的一个最长公共子序列
2)如果xm!= yn，且zk != xm,那么Z是xm-1与yn的一个最长公共子序列
3)若果xm != yn,且zk != yn, 那么Z是xm与yn-1的一个最长公共子序列
所以状态转移方程如下(本来画了图表示的，但是图没有显示，暂且这样吧)：
dp[i,j] =<1> 0ifi=0或者j =0
<2> dp[i-1, j-1] + 1if i , j >0 and xi = yj
<3>max(dp[i-1][j], dp[i][j-1])ifi, j > 0 and xi != yj
根据上述状态方程，以序列X[1…n]和Y[1…n]为输入参数，输出参数有dp[i][j]和path[i][j]
其中dp[i][j]表示X[0…i]和Y[0…j]的最长公共子序列的长度，path[i][j]标志着dp[i][j]值是如何取得的，也就是最长公共子序列的路径，即
文章图片
path[i, j] = <1>1if i , j >0 and xi = yj
<2>2if i, j >0 and xi != yj and dp[i-1, j] > dp[i, j-1]
文章图片
<3>3if i, j >0 and xi != yj and dp[i-1, j] < dp[i, j-1]
最长公共子序列的代码如下：
int LCS(int X[], int xlen, int Y[], int ylen)
{
int i, j;
int maxlen;
memset(dp, 0,sizeof(dp));
memset(path, 0,sizeof(path));
maxlen = 0;
for(i = 1;
i <= xlen;
++i)
{
for(j = 1;
j<= ylen;
++j)
{
if(X[i-1]== Y[j-1])
{
dp[i][j]= dp[i-1][j-1] +1;
path[i][j]= 1;
}
else if(dp[i-1][j]> dp[i][j-1])
{
dp[i][j]= dp[i-1][j];
path[i][j]= 2;
}
else
{
dp[i][j]= dp[i][j-1];
path[i][j]= 3;
}
if(dp[i][j]> maxlen)
{
maxlen= dp[i][j];
}
}
}
【最长递减子序列】return maxlen;
}
LCS可以在O(n^2)的时间内序列X={x1,x2,..xm}和Y={y1,y2,…,yn}最长递减序列的长度，同时搜索path[][]数组可以找到最长非递增子序列， 方法如下：
1）当path[i][j]= 1,表示x[i]==y[j],那么Xi和Yj的最长公共子序列就是在Xi-1和Yj-1的基础上加上Xi或者Yj得到的
2）当path[i][j]= 2,表示x[i]==y[j],那么Xi和Yj的最长公共子序列就是Xi-1和Yj的最长公共子序列
3）当path[i][j]= 3,表示x[i]==y[j],那么Xi和Yj的最长公共子序列就是Xi和Yj-1的最长公共子序列
代码如下：
void LCS_path(int path[][NSIZ], int X[], int i, int j)
{
if(i <= 0 || j<= 0)
{
return;
}
if(path[i][j] == 1)
{
LCS_path(path,X, i-1, j-1);
printf("%d", X[i-1]);
}
else
{
if(path[i][j]== 2)
{
LCS_path(path,X, i-1, j);
}
else
{
LCS_path(path,X, i, j-1);
}
}
}
2.1.2测试
测试代码如下：
#include
#include
using namespace std;
#define NSIZ 120
int dp[NSIZ][NSIZ];
int path[NSIZ][NSIZ];
int cmp(int a, int b)
{
return a > b;
}int LCS(int X[], int xlen, int Y[], int ylen)
{
int i, j;
int maxlen;
memset(dp, 0, sizeof(dp));
memset(path, 0, sizeof(path));
maxlen = 0;
for(i = 1;
i <=xlen;
++i)
{
for(j = 1;
j<= ylen;
++j)
{
if(X[i-1]== Y[j-1])
{
dp[i][j]= dp[i-1][j-1] +1;
path[i][j]= 1;
}
else if(dp[i-1][j]> dp[i][j-1])
{
dp[i][j]= dp[i-1][j];
path[i][j]= 2;
}
else
{
dp[i][j]= dp[i][j-1];
path[i][j]= 3;
}if(dp[i][j]> maxlen)
{
maxlen= dp[i][j];
}
} } return maxlen;
}void LCS_path(int path[][NSIZ], int X[], int i, int j)
{
if(i <= 0 || j<= 0)
{
return;
} if(path[i][j] == 1)
{
LCS_path(path,X, i-1, j-1);
printf("%d", X[i-1]);
}
else
{
if(path[i][j]== 2)
{
LCS_path(path,X, i-1, j);
}
else
{
LCS_path(path,X, i, j-1);
}
}
}int main()
{
int X[] = {9, 4, 3,2, 5, 4, 3, 2};
int Y[NSIZ];
int maxlen;
int n = sizeof(X)/sizeof(X[0]);
memcpy(Y, X, n * sizeof(int));
sort(Y, Y + n,cmp);
maxlen = LCS(X, n, Y, n);
LCS_path(path, X, n, n);
return 0;
} 2.2直接根据动态转移方程解决 2.2.1 原理
典型的DP问题，设原数组X[1…n],另设辅助数组dp[i]表示从i到n这一段中以n结束的最长递减子序列的长度，设定初始的dp[i]=1(0 <= i
函数代码:
int longest_decrease_seq(int X[], int n)
{
int i, j;
int maxlen;
for(i = 0; i <=n; ++i)
{
dp[i] = 1;
}
maxlen = dp[0];
for(i = n-1; i >=0; --i)
{
for(j = i + 1; j < n; ++j)
{
if(X[i]> X[j])
{
dp[i] =max(dp[i], dp[j] + 1);
if(maxlen< dp[i]) //更新最长的序列的长度。
{
maxlen= dp[i];
}
}
}
}
//输出最大递减子序列
for(j = 0; j
if(dp[j] ==maxlen)
{
printf("%d", X[j]);
maxlen--;
}
}
return maxlen;
}
2.2.2测试
#include
using namespace std;
#define NSIZ 1200int dp[NSIZ];
//d[i]表示从num[i]到num[n]之间的最长子序列的长度。int longest_decrease_seq(int X[], int n)
{
int i, j;
int maxlen;
for(i = 0;
i <=n;
++i)
{
dp[i] = 1;
} maxlen = dp[0];
for(i = n-1;
i >=0;
--i)
{
for(j = i + 1;
j < n;
++j)
{
if(X[i]> X[j])
{
dp[i] =max(dp[i], dp[j] + 1);
if(maxlen< dp[i]) //更新最长的序列的长度。
{
maxlen= dp[i];
}
}
}
}
//输出最大递减子序列
for(j = 0;
j 2.3 对方法2的改进算法 2.3.1 原理
这里参考了http://qiemengdao.iteye.com/blog/1660229的博文；
在方法2中，在X[i+1…n]中寻找满足条件X[i]> X[j]时最大的dp[j]时，采用的顺序查找算法时间复杂度为O(n), 现在我们用一个数组C[1…k]保存这从第1个元素到第i个元素的最长递减序列，这样数组C[]的长度就是最后的最长递减子序列的长度。
举个例子说明：
X[] = {9，4，3，2，5，4，3，2},
1)对于X[1]放到C[1]中，C[1]是有序的， 即C[1] = 9,只有一个元素时最长递减序列为9，clen=1;
2)对于X[2],由于X[2] < C[1]那么直接把X[2]放到C[clen++]处，此时clen=2;
同理对X[3], x[4],此时C[] ={9,4, 3, 2}，那么clen=4;
3)对于X[5] =5, X[5]>C[clen-1]=2, 那么在已经排序的C中查找，则X[5]应该在C[2]位置，那么C[2]直接被替换为X[5],现在C[]={9, 5, 3, 2}, clen=4;
4)对于X[6] =4, X[5]>C[clen-1]=2, 那么在已经排序的C中查找，则X[5]应该在C[3]位置，那么C[3]直接被替换为X[6],现在C[]={9, 5, 4, 2}, clen=4;
5)对于X[7] =3, X[5]>C[clen-1]=2, 那么在已经排序的C中查找，则X[5]应该在C[4]位置，那么C[4]直接被替换为X[7],现在C[]={9, 5, 4, 3}, clen=4;
6)对于X[8] =2, X[5]
在C[]中查找的过程，是替换原来的值而不用移动，所以利用二分查找过程，使得整个算法的时间复杂度为O(nlgn);
关键代买如下：
//注意C[]为递减序列,左边大，右边小
int binary_search(int c[], int n, int key)
{
int left,right, mid;
left = 0,right = n-1;
while(left<= right)
{
mid =left + (right -left) /2 ;
if(key== c[mid])
{
returnmid;
}
elseif (key < c[mid]) //当c[mid]大于key时，应该往右边找
{
left= mid + 1;
}
else当c[mid]小于key时，应该往左边找
{
right= mid - 1;
}
}
returnleft;
}
int longest_decrease_seq(int X[], int n)
{
int i, j;
int clen;
intC[NSIZ];
C[0] =X[0];
clen = 1;
for(i =1; i < n; ++i)
{
if(X[i]< C[clen-1])
{
C[clen++]= X[i];
}
else
{
j=binary_search(C, clen, X[i]);
C[j]= X[i];
}
}
//输出最大递减子序列
for(i =0; i < clen; ++i)
{
printf("%d", C[i]);
}
returnclen;
}
2.3.2测试
#include
#include
#include
using namespace std;
#define NSIZ 1200
int C[NSIZ];
//保存着从X[1]到X[i]最长公共序列
//注意C[]为递减序列,左边大，右边小
int binary_search(int c[], int n, int key)
{
int left, right, mid;
left= 0, right = n-1;
while(left<= right)
{
mid= left + (right -left) /2 ;
if(key== c[mid])
{
return mid;
}
else if (key < c[mid]) //当c[mid]大于key时，应该往右边找
{
left = mid + 1;
}
else当c[mid]小于key时，应该往左边找
{
right = mid - 1;
}
}
return left;
}
int longest_decrease_seq(int X[], int n)
{
int i, j;
int clen;
int C[NSIZ];
C[0]= X[0];
clen= 1;
for(i= 1;
i < n;
++i)
{
if(X[i]< C[clen-1])
{
C[clen++]= X[i];
}
else
{
j=binary_search(C, clen, X[i]);
C[j]= X[i];
}
}
//输出最大递减子序列
for(i= 0;
i < clen;
++i)
{
printf("%d", C[i]);
}
return clen;
}
int main()
{
int X[] = {9, 4, 3, 2, 5, 4, 3, 2};
int n = sizeof(X)/sizeof(X[0]);
longest_decrease_seq(X,n);
return 0;
}
