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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 给定数组的最长严格上升子序列的长度。
# @param arr int整型一维数组 给定的数组
# @return int整型
#
from bisect import bisect_left
class Solution:
    def LIS(self , arr: List[int]) -> int:
        # write code here
        g = []
        if len(arr) == 0: return 0
        for x in arr:
            j = bisect_left(g, x)
            if j == len(g):
                g.append(x)
            else:
                g[j] = x
        return len(g)