LeetCode 第 300 题：最长上升子序列

（以下题解根据我自己在评论区的回答修改而成，并且添加了“二分查找 + 贪心算法”的思路。）

首先仔细审题，明确题目中的条件。

1、子序列：不要求连续子序列，只要保证元素前后顺序一致即可；

2、上升：这里的“上升”是“严格上升”，类似于 [2, 3, 3, 6, 7] 这样的子序列，因为 3 重复了，所以不是“严格上升”的；

一个序列可能有多个最长上升子序列，题目中只要我们求这个最长的长度。如果使用回溯搜索，选择所有的子序列进行判断，时间复杂度为 。

这个问题具有最优子结构，因此可以考虑使用动态规划完成。

动态规划

定义状态：dp[i] 表示以第 i 个数字为结尾的最长上升子序列的长度。即在 [0, ..., i] 的范围内，选择以数字 nums[i] 结尾可以获得的最长上升子序列的长度。注意：以第 i 个数字为结尾，即要求 nums[i] 必须被选取。反正一个子序列一定会以一个数字结尾，那我就将状态这么定义，这一点是常见的。

状态转移方程：遍历到索引是 i 的数的时候，我们应该把索引是 [0, ... ,i - 1] 的 dp 都看一遍，如果当前的数 nums[i] 严格大于之前的某个数，那么 nums[i] 就可以接在这个数后面形成一个更长的上升子序列。把前面的 i 个数都看了， dp[i] 的值就是它们的最大值加 。即比当前数要小的那些里头，找最大的，然后加 。

状态转移方程：dp(i) = max( 1 + dp(j) if j < i and dp[i] > dp[j])。

最后不要忘了，扫描一遍这个 dp 数组，其中最大值的就是题目要求的最长上升子序列的长度。

Python 代码：

class Solution:

    # 将 dp 数组定义为：以 nums[i] 结尾的最长上升子序列的长度
    # 那么题目要求的，就是这个 dp 数组中的最大者
    # 以数组  [10, 9, 2, 5, 3, 7, 101, 18] 为例
    # dp 的值： 1  1  1  2  2  3  4    4

    def lengthOfLIS(self, nums):
        size = len(nums)
        # 特判
        if size <= 1:
            return size
        
        dp = [1] * size
        for i in range(1, size):
            for j in range(i):
                if nums[i] > nums[j]:
                    # + 1 的位置不要加错了
                    dp[i] = max(dp[i], dp[j] + 1)
        # 最后要全部一看遍，取最大值
        return max(dp)

二分查找 + 贪心算法

300-1.jpg 300-2.jpg 300-3.jpg

每一次来一个新的数 num，就找 tail 数组中大于等于 num 的那个数，试图让它变小，以致于新来的数有更多的可能性接在它后面，成为一个更长的“上升子序列”，这是“贪心算法”的思想。

Python 代码：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        size = len(nums)
        if size < 2:
            return size
        
        tail = []
        for num in nums:
            # 找到大于等于 num 的第 1 个数
            l = 0
            r = len(tail)
            while l < r:
                mid = l + (r - l) // 2
                if tail[mid] < num:
                    l = mid + 1
                else:
                    r = mid 
            if l == len(tail):
                tail.append(num)
            else:
                tail[l] = num
        return len(tail)

（本题完）