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

使用 dp 的思路会超时,利用二分法查找每个数所在的位置,最终排序数组的长度即为最长上升子序列的长度

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