题解 | #最长上升子序列(三)#

思路：
先求最长递增子序列长度，再根据长度求字典序最小序列
声明dp[i]: 数组以arr[i]结尾的最长递增序列 对于dp[i], 遍历 arr[1]-arr[i-1], 跟arr[i]比较并取最大值。 即 a[i]>=a[j]: dp[i] = max(dp[i], dp[j]+1); 1<=j<i 其复杂度为O(n^2)

优化：为了避免dp[i]每次都进行比较，用一个数组minele_res来保存之前的递增子序列，确保arr[i]只需要与该数组的最后一个数比较即可得出最长长度，并更新这个数组，利用空间换取时间
minele_res数组每次有最优的子序列时，用二分法找到位置并更新，具体如代码

class Solution:
    def BinSearch(self, arr, target):
        arr_len = len(arr)
        l, r = 0, arr_len-1
        while l < r:
            mid = int(l + (r - l) / 2)
            if arr[mid] > target:
                r = mid
            else:
                l = mid + 1
        return r

  
    def LIS(self, arr):
        dp = [0] * (len(arr))
        dp[0] = 1
        minele_res = [arr[0]]  # 需要多一个数组来存放长度为i时，对应最小的元素
        for i in range(1, len(arr)):
            if arr[i] > minele_res[-1]:
                minele_res.append(arr[i])
                dp[i] = len(minele_res)
            else:
                pos = self.BinSearch(minele_res, arr[i])
                minele_res[pos] = arr[i]
                dp[i] = pos + 1  # 这里的dp值为找到的pos+1
        length = len(minele_res)
        for i in range(len(arr) - 1, -1, -1):
            if dp[i] == length:
                minele_res[length - 1] = arr[i]
                length -= 1
                
        return minele_res