如何找到最长递增子序列的实际序列？

Question

这不是家庭作业问题。我正在复习最长递增子序列问题。我在网上到处阅读。我明白如何找到“长度”，但我不明白如何回溯实际序列。我正在使用耐心排序算法来查找长度。谁能解释如何找到实际的序列？我不太明白维基百科上的版本。有人可以用不同的方法或不同的方式解释吗？

谢谢。

Answer 1

让我们将 max(j) 定义为 A[j] 之前的最长递增子序列。有两种选择：或者我们在这个子序列中使用 A[j]，或者我们不使用。

如果我们不使用它，那么该值将为 max(j-1)。如果我们确实使用它，那么该值将是
max(i)+1，当 i 是最大索引且 i < 时j 且 A[i] ＜ A[j]。 （这里我们假设 max(i) 序列使用 i- 不一定为真，但我们可以通过为每个单元保存 2 个值来解决这个问题 - max(j) 值和 max*(j)，当 max*( j) 是使用 A[j] 的最长递增子序列，每次都会计算 max*(i)+1)。

综上所述，计算 max(j) 的递归公式为：
max{max(j-1),max*(i)+1}，且max*(j)=max*(i)+1。
在每个数组单元中，您可以保存一个指针，该指针告诉您是否选择使用 A[j] 单元。 这样就可以在数组上向后移动的同时找到所有的序列。

时间复杂度：递归公式以及查找最后的序列的复杂度为 O(n ）。这里的问题是为每个 A[j] 找到相应的 A[i]，使得 i 是最大索引，使得 i < 。 j，A[i]＜ A[j]。
当然，你可以在 O(n^2) 中天真地做到这一点（从每个单元格向后移动，直到找到这个 i）。如果你想做得更好，那么我很确定你可以通过以下方式在 O(nlogn) 中完成：

*对数组进行排序。
1）寻找数组中最小的整数，并将数组中的位置记为k。

2）对于A[k+1]，我们当然有A[k] < A[k+1]。如果 A[k+1]>A[k+2]，则 k 也将到达第 k+2 个单元格，依此类推，直到 A[k+m] < A[k+m+1]，然后k+m是k+m+1的英尺，

3）删除您在上一阶段找到的相应单元格中的所有单元格

4）返回到1。

希望它有帮助。 请注意，这是我独自思考的，因此这里出现错误的可能性很小 - 请相信我是对的，如果需要，请要求更多说明。

Answer 2

此 Python 代码解决了最长递增序列问题，并且还返回此类序列之一。诀窍是，在填充动态规划表的同时，另一个数组也被填充，存储用于构造最佳解决方案的元素的索引。

def an_lis(nums):
    table, solution = lis_table(nums)
    if not table:
        return (0, [])
    n, maxLen = max(enumerate(table), key=itemgetter(1))
    lis = [nums[n]]
    while solution[n] != -1:
        lis.append(nums[solution[n]])
        n = solution[n]
    return lis[::-1]

def lis_table(nums):
    n = len(nums)
    table, solution = [0] * n, [-1] * n
    for i in xrange(n):
        maxLen, maxIdx = 0, -1
        for j in xrange(i):
            if nums[j] < nums[i] and table[j] > maxLen:
                maxLen, maxIdx = table[j], j
        table[i], solution[i] = 1 + maxLen, maxIdx
    return (table, solution)