LeetCode in Python 300. Longest Increasing Subsequence (最长递增子序列)

求最长递增子序列是深度优先搜索(DFS)的一种应用，有两种比较好的方法可以解决。第一种是动态规划法，时间复杂度为O(n*n)，即设置边界条件和更新迭代公式求解最优解。第二种使用二分查找将时间复杂度降为O(nlogn)。本文给出两种方法的实现代码及说明。

示例：

图1 最长递增子序列输入输出示例 

方法一：

动态规划法

class Solution:
    def lengthOfLIS(self, nums):
        LIST = [1] * len(nums)
        
        for i in range(len(nums) - 1, -1, -1):
            for j in range(i + 1, len(nums)):
                if nums[i] < nums[j]:
                    LIST[i] = max(LIST[i], 1 + LIST[j])
        return max(LIST)

解释：

1）LIST为存储从每个元素出发能得到的最长递增子序列：

        LIST = [1] * len(nums)

        LIST初始值为1，即该数组元素本身作为序列值。

2）接着开始动态规划，如果该元素大于其下一个元素，即表明下一个元素可以成为递增子序列的一员跟该元素放在一起。此时，规划的对象就由该元素移至下一个元素，直至不满足判断条件。

        for i in range(len(nums) - 1, -1, -1):

                for j in range(i + 1, len(nums)):

                        if nums[i] < nums[j]:

                                LIST[i] = max(LIST[i], 1 + LIST[j])

        这里需要注意数组元素下标和两层循环的遍历区间

方法二：

代码：

class Solution:
    def lengthOfLIS(self, nums):
        LIST = []
        
        for x in nums:
            i = self.bisect_left(LIST, x)
            if i == len(LIST):
                LIST.append(x)
            else:
                LIST[i] = x
        return len(LIST) 

    def bisect_left(self, LIST, x):
        l, r = 0, len(LIST)
        while l < r:
            mid = (l + r) // 2
            if LIST[mid] < x:
                l = mid +1
            else:
                r = mid
        return l

1）该方法图解见下图：

图2 方法二图解（图源@花花酱） 

简而言之，按顺序判断数组每个元素，如果该元素大于已加入的所有元素，则直接append到LIST数组结尾，反之替换数组中不影响数组长度的最大元素。举例说明，如上图，遍历至5，可替换上一步加入的8且数组长度依然为3。

2）使用了二分查找寻找遍历到的当前元素应该插入的位置。

        def bisect_left(self, LIST, x):

                l, r = 0, len(LIST)

                while l < r:

                        mid = (l + r) // 2

                        if LIST[mid] < x:

                                l = mid +1

                        else:

                                r = mid

                return l

关于 bisect_left和bisect_right等的具体实现算法及区别见下方：

        bisect_left,bisect_right,bisect的用法，区别以源码分析_bisect_right(arr,arr[i]+k,i)-CSDN博客