300. 最长上升子序列

题目

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

示例:

输入: [10,9,2,5,3,7,101,18]

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

动态规划

最简单的动态规划，一个一个读入数据，维护一个数组代表该数字读入后，目前最长的上升子序列有多长。转移条件是：
当前面的数字比当前数字小，那些数字对应的长度里面，最大的数字+1。
举个例子，[9,2,5,3,7,101,18]中：

初始状况
nums = []
length = []
--------------------
第一步：
nums = [9]
length = [1]
--------------------
第二步：
nums = [9,2]
length = [1,1]
假如nums只有这两个，那么能找出的最长上升串只有9或者2，也就是长度为1.
--------------------
第三步：
nums = [9,2,5]
length = [1,1,2]
比5大的只有2，那么5对应的长度就是在数字2对应的长度+1，这时候最长串是`2,5`
--------------------
第四步：
nums = [9,2,5,3]
length = [1,1,2,2]
--------------------
第五步：
nums = [9,2,5,3,7]
length = [1,1,2,2,3]
以此类推

代码部分：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        length = [1]*len(nums)
        max_length = 0
        for i in range(len(nums)):
            pre_max = 0
            for j in range(i):
                if nums[j] < nums[i] and pre_max < length[j]:
                    pre_max = length[j]
            length[i] = pre_max +1
            if length[i] > max_length:max_length=length[i]
        return max_length

贪心+二分

这个解释起来麻烦一点，基本是也是动态规划的改进版。不过这个时候维护的列表不是读到某个字符时最长串的长度，而是目前最长串是什么样。比如[1,2,9,10,5,6,7,8]最长串为[1,2,5,6,7,8]。在计算过程中我们并不知道最长串是什么样，但是我们可以根据目前的条件完善最长串。解释不易，看个例子就都懂了。

第1步：
目前的数组：[1]
维护的最长串：[1]
-------------------
第2步：
目前的数组：[1,2]
维护的最长串：[1,2]
-------------------
第3步：
目前的数组：[1,2,9]
维护的最长串：[1,2,9]
-------------------
第4步：
目前的数组：[1,2,9,10]
维护的最长串：[1,2,9,10]
-------------------
第5步：
目前的数组：[1,2,9,10,5]
维护的最长串：[1,2,5,10]
这一步划重点！读到5的时候，我们可以知道实际上的最长串还是[1,2,9,10]这四个数字。
但是，后面的5意味着，如果后面有很多介于5到9之间的数字，实际上最后的答案会变成[1,2,5,6...]。
如果后面都是一些极大的数，最后的最长串还是[1,2,9,10,...]。
但是目前在这一步并不确定后面有什么的情况下，我们把5插入到维护的最长串中，替换掉一个比它大但是最接近5的数。
实际上这并不是此时的最长串，但是答案要求的仅仅是长度，而替换并不改变最长串的长度。
这样的插入好处在于：如果后面还有在5-10中间的数字，那么我们可以用那个数字把10替换掉，然后逐步替换成正确的答案。
实际上这个5还有另一种解释，5排在第三个位置，如果我们从当前已知的数组中找出长度为3的子串，有[1,2,9] [1,2,5] [1,2,10],[2,9,10].而5是这些里面最小的数字。
-------------------
第6步：
目前的数组：[1,2,9,10,5,6]
维护的最长串：[1,2,5,6]
-------------------
第7步：
目前的数组：[1,2,9,10,5,6,7]
维护的最长串：[1,2,5,6,7]
-------------------
依次到最后。

实际上维护的最长串是个递增的数组，这样插入（替换）的时候就可以用二分法查找。

代码：

class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if not nums:
            return 0
        string = [nums[0]]
        for num in nums:
            # 二分法查找插入点
            i, j = 0,len(string)
            while i < j  :
                m = (i+j)//2
                if string[m] < num: i = m+1 # 替换更大的数字，所以可以+1，不然可能死循环
                else: j = m
            if i >= len(string): string.append(num)
            else: string[i] = num
        return len(string)

总结

用在长度为i的子串末尾的数字来作为表格很关键。