最长上升子序列(一)

[编程题]最长上升子序列(一)

热度指数：62510 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 $i$ 和 $j$ 满足 $i<j$ 且 $arr_i \geq arr_j$ 。

数据范围： $0\leq n \leq 1000$

要求：时间复杂度 $O(nlogn)$ ，空间复杂度 $O(n)$

示例1

输入

[6,3,1,5,2,3,7]

输出

说明

该数组最长上升子序列为 [1,2,3,7] ，长度为4

算法知识视频讲解

Python 3

蓝鲸与风

class Solution:
    def LIS(self , arr: List[int]) -> int:
        #设置数组长度大小的动态规划辅助数组
        dp = [1 for i in range(len(arr))] 
        res = 0
        for i in range(1, len(arr)):
            for j in range(i):
        #可能j不是所需要的最大的，因此需要dp[i] < dp[j] + 1
        #遍历数组中所有的数，再遍历当前数之前的所有数，只要前面某个数小于当前数，
        #则要么长度在之前基础上加1，要么保持不变，取两者中的较大者
                if arr[i] > arr[j] and dp[i] < dp[j] + 1: 
                    #i点比j点大，理论上dp要加1
                    dp[i] = dp[j] + 1 
                    #找到最大长度
                    res = max(res, dp[i]) 
        return res

发表于 2022-08-21 19:28:45 回复(0)

Python 3

铁离子

class Solution:
    def LIS(self , arr: List[int]) -> int:
        # write code here
        cnt = [-int(1e9+7)]
        for n in arr:
            if n>cnt[-1]:
                cnt.append(n)
            else:
                left = 0
                right = len(cnt)-1
                while left<right:
                    mid = (left+right+1)//2
                    if cnt[mid]>=n:
                        right = mid-1
                    else:
                        left = mid
                cnt[left+1] = n
        return len(cnt)-1

发表于 2022-06-22 17:26:39 回复(0)

Python 3

Vivimore

class Solution:
    def LIS(self , arr: List[int]) -> int:
        res = 0
        n = len(arr)
        dp = [1 for i in range(n)]
        for i in range(1, n):
            for j in range(i):
                if arr[i] > arr[j] and dp[j]+1 > dp[i]:
                    dp[i] = dp[j]+1
                    res = max(res, dp[i])
        return res

发表于 2022-05-22 16:21:56 回复(0)

Python 3

JSFaner

class Solution:
    def LIS(self , arr: List[int]) -> int:
        if not arr: return 0 
        n = len(arr)
        dp = [1]*n 
        for i in range(n-1):
            for j in range(i+1,n):
                if arr[i]<arr[j]:
                    dp[j] = max(dp[i]+1,dp[j]) 
        return max(dp)

发表于 2022-02-25 10:36:06 回复(0)