示例 1:
输入:target = [5,1,3], arr = [9,4,2,3,4]
输出:2
解释:你可以添加 5 和 1 ,使得 arr 变为 [5,9,4,1,2,3,4] ,target...示例 2:
输入:target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
输出:3
提示:
1 <= target.length, arr.length <=...其中一个经典的性质就是:当其中一个数组元素各不相同时,最长公共子序列问题(LCS)可以转换为最长上升子序列问题(LIS)进行求解。...同时最长上升子序列问题(LIS)存在使用「维护单调序列 + 二分」的贪心解法,复杂度为
。...本质是利用「当其中一个数组元素各不相同时,这时候每一个“公共子序列”都对应一个不重复元素数组的下标数组“上升子序列”,反之亦然」。
我们可以使用题目给定的两个数组(
和
)理解上面的话。