线性DP·最大公共上升子序列标准题解

#include <iostream>
using namespace std;
const int N=5005;
int n,a[N],b[N],dp[N],ans;
signed main(){
	scanf("%d",&n);
    // 输入n
    
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
    // 输入串a
    
	for (int i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}
    // 输入串b
    
	for (int i=1;i<=n;i++){
		int maxn=0;
        // 定义最大值
        
		for (int j=1;j<=n;j++){ //枚举串a
			if (a[i]==b[j]){
				dp[j]=max(dp[j],maxn+1);
                // 如果当前两个位置的元素相同, 更新dp[i]   
                
			}
			else if (a[i]>b[j]){ //枚举串b
				maxn=max(maxn,dp[j]);
                // 如果串a的该位置元素大于串b的该位置元素, 更新maxn
                
			}
			ans=max(ans,dp[j]);
            //更新最大长度
            
		}
	}
	printf("%d\n",ans);
    //输出答案

	return 0;
}