难度：中等

题目内容：

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

题解：

这个我一想，找到每个极大值然后刷新数组不就行了，O(n)就可以解决啊
不过再一看题好像不是，间断的也算。
那就麻烦一些，来试试看，简单的算法肯定是O(n^2)，也就是说把每一个当作最大值，然后去算这种情况下的上升序列长多少。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        sublen = []
        for i in range(len(nums)):
            sublen.append(1)
            for j in range(i):
                if nums[j] < nums[i]:
                    if sublen[j] + 1 > sublen[i]:
                        sublen[i] = sublen[j] + 1  #前面最长上升子序列+1
        return max(sublen)

不过耗时肯定不理想，再来看如果用O(nlogn)的话，那肯定是加入了二分法才会出现log
构建一个空数组，然后每次探索到新值的时候如果比最大值还大就插到最后，如果不是的话就替换掉前面比他大的最小的那个数，而二分法就是用在这个查找位置的地方。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        sublen = [nums[0]]
        for num in nums:
            if num > sublen[-1]:
                sublen.append(num)#添加更大的
            else:
                i = 0
                j = len(sublen)-1 #i为小指针，j为大指针
                m = (i+j)//2
                while j>i:
                    print(m)
                    if sublen[m] >= num: 
                        j = m
                    else :
                        i = m + 1
                    m = (i+j)//2
                    print(i,j)
                sublen[i] = num
            print(sublen)
        return len(sublen)