我要招人

去企业版

首页 > 试题广场 >

最长上升子序列(一)

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

热度指数：62051 时间限制：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

算法知识视频讲解

Python3

勇敢小小小牛

在函数中，我们首先检查数组是否为空，如果为空，则返回0。然后，我们初始化一个dp数组，其长度与输入数组相同，并将所有元素初始化为1，因为每个元素本身可以看作是一个长度为1的子序列。

接下来，我们遍历输入数组，对于每个位置i，我们再遍历它之前的所有位置j，如果arr[i]大于arr[j]，说明我们可以将arr[i]添加到以arr[j]结尾的子序列中，从而可能形成一个更长的子序列。因此，我们尝试更新dp[i]为dp[j] + 1（即以arr[j]结尾的子序列长度加1）。

最后，我们返回dp数组中的最大值，它代表整个数组的最长严格上升子序列的长度。

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

发表于 2024-03-16 11:33:12 回复(0)

Python3

牛客429226965号

class Solution:

def LIS(self , arr: List[int]) -> int:

if len(arr) == 0:

return 0

n = len(arr)

dp = [1] * n

maxVal = 0

for i in range(n):

for j in range(i):

if arr[j] < arr[i]:

dp[i] = max(dp[i], 1 + dp[j])

maxVal = max(maxVal, dp[i])

return maxVal

发表于 2023-08-10 16:41:59 回复(0)

Python3

Namely

class Solution:
    def LIS(self , arr: List[int]) -> int:
        # 定义dp[i]为选中第i个元素时，最大的上升子序列长度
        m = len(arr)
        max_length = 0
        dp = [0] * (m+1)
        for i in range(0,m):
            for j in range(i):
                if arr[j] < arr[i]:
                    dp[i] = max(dp[i], dp[j])
            dp[i] += 1
            max_length = max(max_length, dp[i])    
        return max_length

发表于 2023-03-03 16:09:04 回复(0)

Python3

JianYue

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 给定数组的最长严格上升子序列的长度。
# @param arr int整型一维数组 给定的数组
# @return int整型
#
class Solution:
    def LIS(self , arr: List[int]) -> int:
        uplens = [1 for i in arr]
        ret = 0
        for i in range(len(arr)):
            for j in range(0, i):
                if arr[i] > arr[j]:
                    uplens[i] = max(uplens[i], uplens[j] + 1)
            ret = max(ret, uplens[i])
        return ret

发表于 2022-10-02 16:17:20 回复(0)