首页 > 试题广场 >

Array

[编程题]Array

小红有两个长度为n的排列A和B。每个排列由[1,n]数组成，且里面的数字都是不同的。

现在要找到一个新的序列C，要求这个新序列中任意两个位置(i,j)满足:

如果在A数组中C[i]这个数在C[j]的后面，那么在B数组中需要C[i]这个数在C[j]的前面。

请问C序列的长度最长为多少呢？

第一行一个整数，表示N。

第二行N个整数，表示A序列。

第三行N个整数，表示B序列。

满足:N<=50000

输出最大的长度

示例1

输入

5
1 2 4 3 5
5 2 3 4 1

最长的C为1,3,4,5

算法知识视频讲解

Python

月亮上的熊猫

python动态规划之抱头痛哭...

上面的图是我的二维dp，超内存。

思路：把b逆序，求a和b的最长公共子序列，转化为经典动规。

下面的图是[小二郎求offer]的一维dp，超时。

思路：tmp存储a和b的关系，即b的元素在a中的位置。

编辑于 2019-08-20 16:42:17 回复(0)

提交观点

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师 2019 360集团 Java工程师

上传者：小小

难度：

1条回答 40收藏 4358浏览

Array

扫一扫，把题目装进口袋