Leetcode 300. 最长上升子序列
题目描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例 1:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
动态规划
申请等长的临时数组 arr，用于保存每个位置上对应的最长上升序列长度，则计算 arr[i] 时，需要遍历前 i 个位置，取 nums 值小于 nums[i] 的最大序列长度加一，即为 arr[i] 的值。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
length=len(nums)
arr=[1]*length
for i in range(1,length):
for j in range(i):
if nums[i]>nums[j]:
arr[i]=max(arr[i],arr[j]+1)
return 0 if length==0 else max(arr)动态规划+二分法
申请临时数组用于保存上升序列，遍历 nums 数组元素，若元素大于临时数组最大值，则直接添加进临时数组；否则将临时数组中适当位置处元素更新为该元素。
二分法计算元素位置，得到的临时数组位置上的值必然大于该新元素，更新元素值，即将元素值变小，并不影响后续的 nums 数组遍历。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
arr=[nums[0]]
for e in nums[1:]:
if e>arr[-1]:
arr.append(e)
continue
l,r=0,len(arr)-1
while l<=r:
middle=l+(r-l)//2
if arr[middle]<e:
l+=1
elif arr[middle]>e:
r-=1
else:
break
if l>r:
arr[l]=e
return len(arr)本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.06.11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读