本文主要是介绍Leetcode 300. Longest Increasing Subsequence [Python],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
此题是众多LIS相关的母题目。很重要。两种思想求,贪心(NlogN)和DP(N方)
贪心:
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:N = len(nums)res = [float('inf') for _ in range(N)]for i in range(len(nums)):idx = bisect.bisect_left(res, nums[i]) #非严格递增(两个相邻元素可以一样大)用 right,严格递增用left。res[idx] = nums[i]for pos in range(len(res)-1, -1, -1):if res[pos] != float('inf'):return pos + 1return 0
DP:
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if not nums:return 0res = [1 for _ in range(len(nums))]for i in range(1, len(nums)):for j in range(i):if nums[i] > nums[j]:res[i] = max(res[i], res[j]+1)return max(res)
这篇关于Leetcode 300. Longest Increasing Subsequence [Python]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!