子数组指数组中去掉一些元素(也可以不去)并且不改变剩下元素的顺序后产生的数组. 递增子数组指满足元素为递增的子数组. 给到一个数组, 求得最长的递增子数组的长度.
要求复杂度为O(nlogn)
我想了好久没有想出来一个很好的办法, 后来抄别人答案有点搞懂了, 然后又自己写了一遍. 大概是懂了吧, 但是今晚太晚了, 以后再补上我的理解.
以上

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 1
        longest_val_list = []
        longest_index_list = []
        lis_list = []

        longest_val_list.append(nums[0])
        longest_index_list.append(0)
        lis_list.append(1)

        for i in range(1, len(nums)):
            val = nums[i]

            if val > longest_val_list[-1]:
                longest_val_list.append(val)
                longest_index_list.append(i)
                lis_list.append(len(longest_val_list))
                continue
            start = 0
            end = len(longest_val_list) - 1
            while start < end:
                mid = (start + end) // 2
                if longest_val_list[mid] >= val:
                    end = mid
                else:
                    start = mid + 1
            longest_val_list[start] = val
            # # can add or not add
            # longest_index_list[start] = i
            lis_list.append(start + 1)
        # print(lis_list)
        # print(longest_val_list)
        # print(longest_index_list)
        return max(lis_list)