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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
    def LIS(self , arr: List[int]) -> List[int]:
        # write code here
        b = [arr[0]]
        def binary_find(target):
            l, r = 0, len(b) - 1
            while l <= r:
                mid = (l + r) // 2
                if target > b[mid]:
                    l = mid + 1
                else:
                    r = mid - 1
            return l
        
        maxlen = [1]
        for i in arr[1:]:
            if i > b[-1]:
                b.append(i)
                maxlen.append(len(b))
            else:
                idx = binary_find(i)
                b[idx] = i
                maxlen.append(len(b[:idx + 1]))

        length=len(b)
        for i in range(len(arr)-1,-1,-1):
            if maxlen[i]==length:
                b[length-1]=arr[i]
                length-=1
        return b