最长公共上升子序列 LCIS
给你两个长度为n的数组。让你求它们的最长公共上升子序列。 in: 4 2 2 1 3 2 1 2 3 out: 2
#include<bits/stdc++.h> #define LL long long using namespace std; int a[3005], b[3005], f[3005][3005]; int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++){ scanf("%d", &a[i]); } for(int i=1; i<=n; i++){ scanf("%d", &b[i]); } for(int i=1; i<=n; i++){ int mx=0; for(int j=1; j<=n; j++){ f[i][j]=f[i-1][j];//初始化 if(a[i]>b[j]) mx=max(mx, f[i-1][j]); if(a[i]==b[j]) f[i][j]=mx+1; } } int ans=0; for(int i=1; i<=n; i++){ ans=max(ans, f[n][i]); } printf("%d\n", ans); return 0; }