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)