时间戳

首页 > 解决方案 > 如何使这个最长递增子序列程序返回这个子序列

algorithm - 如何使这个最长递增子序列程序返回这个子序列

问题描述

我有这个最长增加子序列的代码。现在它返回最长增加子序列的长度，但我不知道如何让它返回这个确切的子序列。例如。在这种情况下，它应该返回 [3,6,7,8,9]。有任何想法吗？我希望不要使用非常复杂的语法：D

a = [3, 6, 7, 2, 1, 8, 9, 5]
n = len(a)
q = [0] * n
for k in range(n):
    max = 0
    for j in range(k):
        if a[k] > a[j]:
            if q[j] > max:
                max = q[j]
    q[k] = max + 1
return(max(q))

外循环在 a 中的所有元素之后进行迭代，内循环检查表中的元素 k 是否大于索引 0 到 k-1 中的项目多亏了 q 表，这个例子看起来像这样[1,2,3,1,1,4,5,2]我们可以看到first elementmake subsequence of length 1，second一个 make subsequence of length 2(with first element），third elementmakes subsequence of length 3（带有第一个和第二个元素），fourth elementmakes ，subsequence of length 1因为没有一个先前的元素小于它，依此类推。所以基本上在每次迭代中，它都会得到以索引 k 结尾的最长递增子序列的长度

同一程序的较短版本：

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

标签： algorithmsubsequence

解决方案

如果您已经描述了您的代码在做什么，那就太好了，但是据我所知，在每次迭代中，它都会获得以 index 结尾的最长递增子序列的长度k。

要追溯数组中的实际索引，只需添加另一个数组previous[]。

初始化previous = [-1] * n.

进而

if q[j] > max: 
   max = q[j]
   previous[k] = j

推荐阅读