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

class Solution:
    def LIS(self , arr: List[int]) -> List[int]:
        # write code here
        n = len(arr)
        top = [0] * n
        piles = 0
        dp = [1] * n
        for i in range(n):
            poker = arr[i]
            l, r = 0, piles
            while l < r:
                mid = (l + r) // 2
                if poker > top[mid]:
                    l = mid + 1
                else:
                    r = mid
            if l == piles:
                piles += 1
                dp[i] = piles
            else:
                dp[i] = l + 1
            top[l] = poker
            
        
        res = [0] * piles
        for i in range(n-1, -1, -1):
            if dp[i] == piles:
                piles -= 1
                res[piles] = arr[i]

        return res