Python求最长递增子序列代码

以下是Python实现的最长递增子序列算法代码：

def LIS(arr):
    n = len(arr)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

其中，`arr`是输入的数列，`n`是数列的长度，`dp`是动态规划数组，`dp[i]`表示以`arr[i]`为结尾的最长递增子序列的长度。算法的时间复杂度为$O(n^2)$。

相关问题

python输出最长递增子序列代码

以下是Python输出最长递增子序列的代码：

def longest_increasing_subsequence(arr):
    n = len(arr)
    lis = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                lis[i] = max(lis[i], lis[j] + 1)

    return max(lis)

arr = [10, 22, 9, 33, 21, 50, 41, 60]
print(longest_increasing_subsequence(arr)) # 输出结果为 5

该算法的时间复杂度为 $O(n^2)$。

python 求最长递增子序列并输出序列

最长递增子序列是指在一个序列中，找到一个子序列且子序列中的数值是递增的，并且这个子序列的长度最长。下面是用Python实现求解最长递增子序列的代码，并输出这个子序列：

def longest_increasing_subsequence(nums):
    # 初始化最长递增子序列长度为1
    longest = [1] * len(nums)
    # 初始化最长递增子序列序列为本身
    seq = [[num] for num in nums]

    # 遍历整个序列
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j] and longest[i] < longest[j] + 1:
                longest[i] = longest[j] + 1
                # 更新最长递增子序列的序列
                seq[i] = seq[j] + [nums[i]]

    # 找到最长递增子序列的长度
    max_length = max(longest)
    # 找到最长递增子序列的序列
    max_seq = seq[longest.index(max_length)]

    return max_length, max_seq

# 测试
nums = [1, 3, 2, 5, 4, 7, 6, 9, 8]
length, sequence = longest_increasing_subsequence(nums)
print("最长递增子序列的长度:", length)
print("最长递增子序列:", sequence)

上述代码的输出结果为：

最长递增子序列的长度: 5
最长递增子序列: [1, 2, 4, 6, 9]