#3981
1306. 最长公共子上升序列
1306. 最长公共子上升序列
题目描述
给定两个整数序列,求它们的最长公共上升子序列。 长度为 的序列 是 的上升子序列,当且仅当存在 ,使所有 都满足 ,且所有 满足 。 公共子序列必须同时是两个输入序列的子序列。
输入格式
每个序列用两行表示,第一行是长度 ,第二行是该序列的M个整数 。
输出格式
在第一行,输出两个序列的最长上升公共子序列的长度 。在第二行,输出该子序列。如果有不止一个符合条件的子序列,则输出任何一个即可;L=0 时第二行为空行。不得输出额外内容。
5
1 4 2 5 -12
4
-12 1 2 4
2
1 4
提示
经典算法Baidu搜索,深刻体会。
来源
一本通在线评测 ybtbas-1306