博客

import bisect
class Solution:
    def LIS(self , arr ):
        # write code here
        max_len = [1] * len(arr)
        max_arr = [arr[0]]
        for i in range(1, len(arr)):
            if arr[i] > max_arr[-1]:
                max_arr.append(arr[i])
                max_len[i] = len(max_arr)
            else:
                idx = bisect.bisect_left(max_arr, arr[i])
                max_arr[idx] = arr[i]
                max_len[i] = idx + 1
        
        res = []
        MAX = max(max_len)
        for i in range(len(max_len) - 1, -1, -1):
            if max_len[i] == MAX:
                res.append(arr[i])
                MAX -= 1
        return res[::-1]