每日一题-14

题目描述

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

示例:

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

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

解题思路

1.动态规划。设置一个dp数组，dp[i]表示以第i个元素为结尾的最长上升子序列的长度。
由于本题所求的是最长上升子序列，子序列不一定需要连续，所以在设置状态转移的时候，不能简单的认为dp[i]=max(dp[i],dp[i-1]+1)。因为不连续，所以dp[i]不止只与dp[i-1]有关。
所以在求dp[i]的时候，我们需要遍历dp[0...i]的所有值，最后得到的max(dp[i], dp[0...i])才是我们所需要的dp[i]。
最后，也是因为子序列的不连续性，所以以最后一个元素为结尾的最长上升子序列不一定是最大的。所以在最后我们需要求出dp中的最大值，才是这个数组的最大上升子序列。
2.耐心排序。思路来源于大佬（labuladong）。代码下方有，思路搜大佬公众号里面有
3.贪心+动态规划
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

代码

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # dp = [1] * (len(nums))
        # for i in range(0,len(nums)):
        #     for j in range(0, i):
        #         if nums[i] > nums[j]:
        #             dp[i] = max(dp[i], dp[j]+1)
        # return max(dp) if dp else 0

        top = [None]*len(nums)
        #牌堆数初始为0
        piles = 0
        for i in range(len(nums)):
            poker = nums[i]#需要摆放的牌
            #左侧边界的二分查找
            left = 0
            right = piles
            while left<right:
                mid = (left+right)//2
                if top[mid] >= poker:
                    right = mid
                else:
                    left = mid+1
            #没遇到合适的牌堆，新建一堆
            if left==piles:
                piles+=1
            #将查找的牌放到查找到的堆顶
            top[left] = poker

        return piles