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 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 lis(arr):
    n = len(arr)
    m = [0]*n
    for x in range(n-2,-1,-1):
        for y in range(n-1,x,-1):
            if arr[x] < arr[y] and m[x] <= m[y]:
                m[x] += 1
    max_value = max(m)
    result = []
    for i in range(n):
        if m[i] == max_value:
            result.append(arr[i])
            max_value -= 1
    return result

arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print(lis(arr))

该代码使用动态规划算法来解决最长递增子序列问题。它首先创建一个长度为n的数组m，其中m[i]表示以arr[i]结尾的最长递增子序列的长度。然后，它使用两个嵌套的循环来计算m数组中的每个元素。对于每个元素x，它将从x+1到n-1的所有元素y与x进行比较。如果arr[x] < arr[y]且m[x] <= m[y]，则将m[x]的值增加1。最后，它找到m数组中的最大值，并使用它来构建最长递增子序列。