最长公共上升子序列 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;
}
全部评论

相关推荐

06-25 16:00
武汉大学 Java
工科研究生底薪工资就开3k啊??
机械打工仔:写文章提成的岗位工资低,你怪工科?
点赞 评论 收藏
分享
星辰再现:裁员给校招生腾地方
点赞 评论 收藏
分享
06-23 11:43
门头沟学院 Java
allin校招的烤冷...:我靠,今天中午我也是这个hr隔一个星期发消息给我。问的问题还是一模一样的😅
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务