Question askedto find the longest common subseq. Technique used-dp,time complexity=O(n^2)
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <utility>
#include <vector>
// five elements
#include <cstdlib>
#include <iomanip>
#define ll long long
#define ef else if
#define rep(i, s, n) for (ll i = s; i < n; i = i + 1)
#define rev(i, s, n) for (int i = s; i > n; i = i - 1)
using namespace std;
#define fr first
#define se second
#define pb push_back
#define mp make_pair
#define mv vector<ll>
#define vv vector<vector<ll>>
#define vii vector<pair<ll, ll>>
#include <functional>
#include <map>
#include <queue>
#include <set>
// akane_psycho
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
#define c1(a) cout << a << endl;
#define c2(a, b) cout << a << " " << b << endl;
#define c4 (k, x, b, c) printf(" %d %d %d %d ", &k, &x, &b, &c)
#define db double
#define inf 1e18
#define lim 2000000000
#define mo 1000000007
#define MAXN 1000001
#define rp(v) \
cout << endl; \
rep(i, 0, v.size()) cout << v[i] << " "; \
cout << endl;
#define lb(v,val) lower_bound(v.begin(),v.end(),val)-v.begin()
#define ub(v,val) upper_bound(v.begin(),v.end(),val)-v.begin()
#define fill(a,d) memset(a,d,sizeof(a))
ll mod(ll n){
return n%(ll)mo;
}
int main()
{
ll t;t=1;while(t--){
ll n,m,p,q;cin>>n>>m;
ll dp[n+1][m+1];
memset(dp,0,sizeof(dp));
ll x[n+1],y[m+1];
rep(i,1,n+1)cin>>x[i];
rep(i,1,m+1)cin>>y[i];
ll mx=0;
rep(i,1,n+1){
rep(j,1,m+1){
if(x[i]==y[j])
{dp[i][j]+=(dp[i-1][j-1]+1);
if(dp[i][j]>mx){
mx=dp[i][j];
p=i;
q=j;
}
//mx=max( mx, dp[i][j] );
}
else {
dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
}
}
}
mv ans;
//c2(p,q)
for(ll i=p;i>=0;i--){//c1(q)
rep(j,0,q+1){
if(dp[i][j]>dp[i-1][j] && dp[i][j]==mx ){ans.pb(x[i]);q=j;mx--;break;}
}
}
for(ll i=ans.size()-1;i>=0;i--)cout<<ans[i]<<" ";
//for(int i=p;i>p-mx;i--)cout<<x[i]<<" ";
//rep(i, p-mx+1 , p+1)cout<<x[i]<<" ";
}
}