300. 最长递增子序列

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/longest-increasing-subsequence/
Star
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
  • 1 <= nums.length <= 2500
  • 104 <= nums[i] <= 104
进阶：
  • 你可以设计时间复杂度为 O(n2) 的解决方案吗？
  • 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

法1 动态规划

思路
典型的动态规划第二类基本型：时间序列加强版.
按照套路，定义dp如下：
  • dp[i]: 以nums[i] 结尾的最长递增子序列长度
状态转移：寻找最优的前驱状态j, 将dp[i] 与dp[j]产生联系
题解
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1 for _ in range(len(nums))]

        for i in range(1, len(dp)):
            for j in range(0, i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)

        return max(dp)
若要得到具体的子序列，那么需要根据得到的do数据来求解，dp数组包括了每一步的决策信息：
  • 第一步，在dp数组中找到最大的 值，且得到其下标k，那么arr[k]就是最长递增子序列的在最后一个元素。
  • 从k往前推，找到另外一个下标j满足 arr[j] < arr[k] 且 dp[j] == dp[k]-1，那么arr[j]就是倒数第二个元素。
  • 依次往前找，直到找到dp[k]个数字。

动态规划 + 二分查找

思路
notion imagenotion image
notion imagenotion image
题解
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # tail[i]: 长度为  i + 1 的最长递增子串的最后一位数字的最小值
        tail = [nums[0]]
        for i in range(1, len(nums)):
            if nums[i] > tail[-1]:
                tail.append(nums[i])
            else:
                # 在 tail中找小于 nums[i]的最大值的下标loc，
                # 然后令 tai[loc+1]为 nums[i]              
                l, r = 0, len(tail)-1
                while l <= r:
                    m = l + (r - l) // 2
                    if tail[m] >= nums[i]:
                        r = m - 1
                    else:
                        l = m + 1
                loc = r + 1
                tail[loc] = nums[i]
        
        return len(tail)
当然，如果向保留 原先的 dp 数组， 也可以加进去
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 以 nums[i] 结尾的最长递增子串的长度
        dp = [1 for _ in nums]

        # tail[i]: 长度为  i + 1 的最长递增子串的最后一位数字的最小值
        tail = [nums[0]]
        for i in range(1, len(nums)):
            if nums[i] > tail[-1]:
                tail.append(nums[i])
                dp[i] = len(tail)
            else:
                # 找 tail 中找第一个 小于 nums[i] 的数字，强其后一位更新为 nums[i]              
                l, r = 0, len(tail)-1
                while l <= r:
                    m = l + (r - l) // 2
                    if tail[m] >= nums[i]:
                        r = m - 1
                    else:
                        l = m + 1
                loc = r + 1
                tail[loc] = nums[i]
                dp[i] = loc + 1
        
        return len(tail)