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

Question

我有一个最长递增子序列的代码。现在它返回最长的递增子序列的长度，但我不知道如何使它返回这个精确的子序列。为了前任。在这种情况下，它应该返回[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]我们可以看到，第一个元素生成长度为1的子序列，第二个元素生成长度为2的子序列（使用第一个元素），第三个元素生成长度为3的子序列（使用第一个和第二个元素），第四个元素生成长度为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