#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N],c;
int a[N],b[N];
int main()
{
    cin>>c;
    for(int i=1;i<=c;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=c;i++)
    {
        cin>>b[i];
    }
    for(int i=1;i<=c;i++)
    {
        for(int j=1;j<=c;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
        }
    }
    cout<<dp[c][c];
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N],c;
int a[N],b[N];
int main()
{
    cin>>c;
    for(int i=1;i<=c;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=c;i++)
    {
        cin>>b[i];
    }
    for(int i=1;i<=c;i++)
    {
        for(int j=1;j<=c;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(a[i]==b[j])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
        }
    }
    cout<<dp[c][c];
}

`#include #include #include #include <unordered_map>

int lengthOfLIS(std::vector& nums) { std::vector lis; for (int num : nums) { auto it = std::lower_bound(lis.begin(), lis.end(), num); if (it == lis.end()) { lis.push_back(num); } else { *it = num; } } return lis.size(); }

int main() { int n; std::cin >> n;

std::vector<int> a(n);
std::vector<int> b(n);

for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
}
for (int i = 0; i < n; ++i) {
    std::cin >> b[i];
}

std::unordered_map<int, int> pos;
for (int i = 0; i < n; ++i) {
    pos[a[i]] = i;
}

std::vector<int> new_b;
for (int num : b) {
    if (pos.find(num) != pos.end()) {
        new_b.push_back(pos[num]);
    }
}

int result = lengthOfLIS(new_b);
std::cout << result << std::endl;

return 0;

} `