最长上升子序列

• 概述

经典的最长上升子序列问题，是求在一个序列中，最长的单增子序列的长度。通过修改一些边界条件，也可以求非严格单增、单减的子序列长度。同时很多问题也可以转化为最长上升子序列问题。
最长上升子序列有两种经典的求解方法，一种基于动态规划，时间复杂度，另一种基于二分查找优化，时间复杂度。
读者可以先练习Leetcode第300号问题。下面给出参考代码。
动态规划

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:  # 严格单增，如果非严格单增，可以改为 >=
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

二分查找

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        d = []
        for a in nums:
            i = bisect.bisect_left(d, a)  # 严格单增，如果非严格单增，可改为bisect_right
            if i < len(d):
                d[i] = a
            else:
                d.append(a)
        return len(d)

• 最长公共子序列与最长上升子序列的相互转化

给你一个数组 target ，包含若干 互不相同 的整数，以及另一个整数数组 arr ，arr 可能 包含重复元素。
每一次操作中，你可以在 arr 的任意位置插入任一整数。比方说，如果 arr = [1,4,1,2] ，那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后面添加整数。
请你返回 最少 操作次数，使得 target 成为 arr 的一个子序列。
一个数组的 子序列 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的子序列（加粗元素），但 [2,4,2] 不是子序列。

数据规模：

target 不包含任何重复元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-operations-to-make-a-subsequence
分析：
本题很容易通过最长公共子序列建模，单最长公共子序列的时间复杂度为，本题所给的数据规模下会超时。因为target中不包含重复元素。所以可以将target中的元素进行编号，然后在arr中寻找最长上升子序列，最长上升子序列的长度就对应着最长公共子序列的长度。对于最长上升子序列问题，使用的算法进行求解。
参考解答：

class Solution:
    def minOperations(self, target: List[int], A: List[int]) -> int:
        def LIS(A):
            d = []
            for a in A:
                i = bisect.bisect_left(d, a)
                if i < len(d):
                    d[i] = a
                else:
                    d.append(a)
            return len(d)
        B = []
        target = { t:i for i, t in enumerate(target)}
        for a in A:
            if a in target: 
                B.append(target[a])
        return len(target) - LIS(B)