最长递增子序列 -- 动规

300. 最长递增子序列

注意「⼦序列」和「⼦串」的区别，⼦串⼀定是连续的，⽽⼦序列不⼀定是连续的。

class LengthOfLIS:"""300. 最长递增子序列https://leetcode.cn/problems/longest-increasing-subsequence/description/"""def solution(self, nums: List[int]):"""方案一: 动态规划辅助数组 dp，dp[i] 表示以nums[i]结尾的子序列的最大长度时间复杂度O(N^2)空间复杂度O(N):param nums::return:"""n = len(nums)dp = [1] * nfor i in range(1, n):tmp = 0for j in range(0, i):if nums[j] < nums[i]:tmp = max(tmp, dp[j])dp[i] = tmp + 1return max(dp)def solution2(self, nums: List[int]):"""方案二：动态规划辅助数组 ends，ends[i] 代表目前所有长度为i+1的递增子序列的最小结尾。可推断出 ends 也是递增序列时间复杂度O(N*logN)空间复杂度O(N):param nums::return:"""if not nums:return 0n = len(nums)ends = [0] * nends[0] = nums[0]l, r, m, right = 0, 0, 0, 0res = 1for i in range(1, n):l = 0r = rightwhile l <= r:m = (l + r) // 2if nums[i] > ends[m]:l = m + 1else:r = m - 1print(right, l)right = max(right, l)ends[l] = nums[i]res = max(res, l + 1)return resdef solution3(self, nums: List[int]) -> int:"""模拟蜘蛛纸牌:param nums::return:"""top = [0] * len(nums)#  牌堆数初始化为 0piles = 0for i in range(len(nums)):poker = nums[i]left, right = 0, pileswhile left < right:mid = left + (right - left) // 2if top[mid] > poker:right = midelif top[mid] < poker:left = mid + 1else:right = mid# 没找到合适的牌堆，新建⼀堆if left == piles:piles += 1# 把这张牌放到牌堆顶top[left] = pokerreturn piles