网站建设上海哪家公司好,抖音视频制作软件,织梦做中英文网站步骤,河南省建设厅网站打不开300. 最长递增子序列 注意「⼦序列」和「⼦串」的区别#xff0c;⼦串⼀定是连续的#xff0c;⽽⼦序列不⼀定是连续的。 class LengthOfLIS:300. 最长递增子序列https://leetcode.cn/problems/longest-increasing-subsequence/description/⼦串⼀定是连续的⽽⼦序列不⼀定是连续的。 class LengthOfLIS:300. 最长递增子序列https://leetcode.cn/problems/longest-increasing-subsequence/description/def solution(self, nums: List[int]):方案一: 动态规划辅助数组 dpdp[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]):方案二动态规划辅助数组 endsends[i] 代表目前所有长度为i1的递增子序列的最小结尾。可推断出 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
