如何使这个最长递增子序列程序return这个子序列

Question

我有最长递增子序列的代码。现在它是最长递增子序列的 return 长度，但是 我不知道如何使它成为 return 这个确切的子序列 。对于前。在这种情况下 它应该 return [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 中的所有元素之后进行迭代，内循环检查 table 中的元素 k 是否大于索引 0 到 k-1 中的项目感谢 q table 这个例子看起来像这样 [1,2,3,1,1,4,5,2] 我们可以看到 first element 使 subsequence of length 1, second 一个使 subsequence of length 2 （与第一个元素），third element 使 subsequence of length 3（具有第一个和第二个元素），fourth element 使 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])

Answer 1

如果您描述了您的代码在做什么，那就太好了，但据我所知，在每次迭代中，它都会获得以索引 k.

结尾的最长递增子序列的长度

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

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

然后

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

如何使这个最长递增子序列程序return这个子序列

How to make this Longest Increasing Subsequence program return this subsequence

algorithm

subsequence