最大上升子序列

布满荆棘的人生 2022-10-20 12:22 122阅读 0赞

# 最长公共子序列 #

## 描述 ##

给定两个整数序列，写一个程序求它们的最长上升公共子序列。  
当以下条件满足的时候，我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , AM 的上升子序列：  
存在 1 <= i1 < i2 < . . . < iN <= M ，使得对所有 1 <= j <=N，均有Sj = Aij，且对于所有的1 <= j < N，均有Sj < Sj+1。

## 输入 ##

每个序列用两行表示，第一行是长度M(1 <= M <= 500)，第二行是该序列的M个整数Ai (-231 <= Ai < 231 )

## 输出 ##

在第一行，输出两个序列的最长上升公共子序列的长度L。在第二行，输出该子序列。如果有不止一个符合条件的子序列，则输出任何一个即可。

### 样例输入 ###

5  
1 4 2 5 -12  
4  
\-12 1 2 4

### 样例输出 ###

2  
1 4

## 思路： ##

此题的切入点就是动态规划，通过dp来确定哪些字符是最长公共子序列中的字符，用d\[i\]\[j\]表示以a数组的前i个元素，b数组的前j个元素并且以b\[j\]为结尾的LCIS的长度。

简单的说就是把a数组的所有值看成矩阵的列，b数组的所有值看成矩阵的行，

如图（一个表格）

B1 B2 B3  
A1 – --  
A2 – --  
设一个二重循环（i在外层，j在内层），

（1）当a\[i\] ！= b\[j\]时， d\[i\]\[j\] = d\[i-1\]\[j\];

这里保证到i、j为止的最大长度不可能小于i-1，j的长度。因为 d\[i\]\[j\] 是以 b\[j\] 为结尾的LCIS，如果 d\[i\]\[j\] > 0 那么就说明 a\[1\] … a\[i\] 中必然至少有一个元素 a\[k\] 等于 b\[j\]。因为 a\[k\] != a\[i\]，那么 a\[i\] 对与d\[i\]\[j\] 无关，、所以在 a\[i\] != b\[j\] 的情况下必然有 d\[i\]\[j\] = d\[i-1\]\[j\]。  
（2）当a\[i\]==b\[j\]时， 首先，这个等于起码保证了长度为1的LCIS。然后我们还需要去找一个最长的且能让b\[j\]接在其末尾的LCIS。之前最长的LCIS在哪呢？首先我们要去找的d数组的第一维必然是i-1。因为i已经拿去和b\[j\]配对去了，不能用了。第二维需要枚举 b\[1\] … b\[j-1\]了，因为你不知道这里面哪个最长且哪个小于 b\[j\]。  
（3）状态转移方程：  
a\[i\] != b\[j\]: dp\[i\]\[j\]=dp\[i-1\]\[j\] ；  
a\[i\] == b\[j\]: dp\[i\]\[j\]=max(d\[i-1\]\[k\]) + 1 ； （1<= k <= j-1）  
（4）But！还没说完，这个算法最关键的是，如果按照一个合理的递推顺序，max(d\[i1\]\[k\])的值我们可以在之前访问 d\[i-1\]\[k\] 的时候通过维护更新一个max变量得到。怎么得到呢？首先递推的顺序必须是状态的第一维在外层循环，第二维在内层循环。也就是算好了 d\[1\]\[n\] 再去算 d\[2\]\[1\]。 如果按照这个递推顺序我们可以在每次外层循环的开始加上令一个max变量为0，然后开始内层循环。当a\[i\]>b\[j\]的时候令max = d\[i-1\]\[j\]。如果循环到了a\[i\] == b\[j\]的时候，则令 d\[i\]\[j\] = max+1。 最后答案是 d\[m\]\[1\] … d\[m\]\[n\]的最大值。

## 算法说明 ##

举个例子讲吧，a：【1 2 3】，b：【2 3】只讲核心部分，即怎么判出的最长公共上升子序列，输入输出部分暂时忽略。  
从i=1的大循环开始，进入循环j=1，mx=6=0.因为两个判断条件都不符合，所以进入下一次循环j=2，同样两个判断条件都不符合，跳出内层循环。  
进入i=2循环的大循环，从j=1开始，dp\[2\]\[1\]=0,sign\[2\]\[1\]=1,此时else if条件符合，所以dp\[2\]\[1\]=1,ans=1。  
而后进入i=2，j=2，两个判断语句都不符合，ans又被置成0。  
最后进入i=3的大循环，首先是j=1，此时符合第一个判断语句，mx置为1，然后进入j=2，  
符合第二个判断语句，注意：这时dp\[3\]\[2\]=mx+1=1+1=2，ans=2，循环结束，代码核心部分结束。  
三、数据结构  
3个一维数组 1个二维数组  
四、算法分析  
不难看到，这是一个时间复杂度为O(n^3)的DP，有点大。。。  
然后还有要注意的一点，因为用的是c++代码，里边有max函数，所以为了避免重名导致Compile Error，要将max改为mx；

###  ###

下面展示一些 `内联代码片`。

#include<iostream>
    #include<algorithm>
    #include<string.h>
    #include<string>//这里也可以用#include<bits/stdc++.h>这个万能头
    using namespace std;
    long long a[501],b[501],z[501];
    int dp[501][501]={
        0},sign[501][501];
    int main(){
        
    	int n,m,i,ans,j,mx,l;
    	cin>>m;
    	for (i=1;i<=m;i++)		
    cin>>b[i];
    	cin>>n;
    	for (i=1;i<=n;i++)
    		cin>>a[i];
    	ans=0;
    	for (i=1;i<=n;i++)
    	{
        
    		mx=0;l=0;
    		for (j=1;j<=m;j++)
    		{
        
    			dp[i][j] = dp[i-1][j];//保证到（i、j）为止的最大长度不可能小于（i-1，j）的
    			sign[i][j] = j;
    			//i不变，遍历j，此时要保证j序列值要小才可以是上升序列
    			if (a[i]>b[j] && mx<dp[i-1][j])
    			{
        	
    				mx=dp[i-1][j];//记录dp[i-1][0~j]的最大值，可以省去内层k的循环
    	            l=j;//记录此时的j值
    			}
    			else if (a[i]==b[j]) 
    			{
        
    				dp[i][j]=mx+1;
    				sign[i][j] = l;
    			}
    			ans=max(ans,dp[i][j]);
    		}
    	}
    	cout<<ans<<endl;
    	int t=1;
    	for (j=2;j<=m;j++)//看作一位数组，找最大的序列的末尾为止，也可以在上面的ans更新时记住
    		if (dp[n][j]>dp[n][t])
    			t=j;
    	int top=0;
    	i=n;j=t;
    	while (dp[i][j])//=0为止
        {
        
    		 while(a[i]!=b[j]&&i) i--;//找到一个相等的值为止
    		 z[top++]=b[j];
    		 j=sign[i][j];
        }
    	for (i=top-1;i>=0;i--)
    		cout<<z[i]<<" ";
    	cout<<endl;
    	return 0;
    }