最长的后续序列

任务是在给定的整数数组中找到最长子序列的长度,使得子序列的所有元素按升序排序。例如, { 15,27,14,38,26,55,46,65,85}的最长增加子序列(LIS)的长度是 6 ,最长的子序列是 {15,27,38,55,65,85} 。再次,对于 {3,4, -1,0,6,2,3 } ,LIS 的长度为 4 ,子序列为 {-1,0,2,3} 。我们将使用动态编程来解决这个问题。

我们来看第二个例子:Item = {3, 4, -1, 0, 6, 2, 3}。我们首先采用与序列大小相同的数组 dp 。如果我们包括原始序列的第 i 项,则 dp [i] 表示 LIS 的长度。在一开始我们知道,对于每个项目,至少最长的增长子序列的长度为 1 。这是通过考虑单个元素本身。所以我们用 1 初始化 dp 数组。我们将有两个变量 ij 。最初将是 1j 将是 0 。我们的数组看起来像: **** **** **** **** **** **** **** **** **** ****

 placeholderCopy3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Value` |  1  |  1  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
           j     i

数组上方的数字代表我们序列的相应元素。我们的策略是:

 placeholderCopyif Item[i] > Item[j]
    dp[i] := dp[j] + 1

这意味着,如果在元件是比元件更大 Ĵ ,包含元件在 LIS 的长度 Ĵ ,将长度增加 1 ,如果我们包括元件在它。在我们的例子中,对于 i = 1j = 0Item [i] 大于 Item [j] 。所以 dp [i] = dp [j] + 1 。我们的数组看起来像:

 placeholderCopy3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Value` |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
           j     i

在每一步,我们将 j 增加到 i ,然后将 j 重置为 0 并递增 i 。现在, j 已到达 i ,所以我们将 i 增加到 2

 placeholderCopy3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Value` |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
           j           i

对于 i = 2j = 0Item [i] 不大于 Item [j] ,所以我们什么都不做并且增加 j

 placeholderCopy3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Value` |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
                 j     i

对于 i = 2j = 1Item [i] 不大于 Item [j] ,所以我们什么都不做,因为 j 已达到其极限,我们递增 i 并将 j 重置为 0

 placeholderCopy3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Value` |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
           j                 i

对于 i = 3j = 0Item [i] 不大于 Item [j] ,所以我们什么都不做并且增加 j

 placeholderCopy3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Value` |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
                 j           i

对于 i = 3j = 1Item [i] 不大于 Item [j] ,所以我们什么都不做并且增加 j

 placeholderCopy3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Value` |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
                       j     i

对于 i = 3j = 2Item [i] 大于 Item [j] ,因此 dp [i] = dp [j] + 1 。之后,由于 j 已达到极限,我们再次将 j 重置为 0 并递增 i

 placeholderCopy3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Value` |  1  |  2  |  1  |  2  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
           j                       i

对于 i = 4j = 0Item [i] 大于 Item [j] ,因此 dp [i] = dp [j] + 1 。之后,我们增加 j

 placeholderCopy3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Value` |  1  |  2  |  1  |  2  |  2  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
                 j                 i

对于 i = 4j = 1Item [i] 大于 Item [j] 。我们还可以注意到 dp [i] = dp [j] + 1 将为我们提供 3 ,这意味着如果我们将 LIS 用于 Item [j] 并使用它添加 Item [i] ,我们将获得更好的 LIS { 3,4,6}比{3,6}之前。所以我们设置 dp [i] = dp [j] + 1 。然后我们增加 j

 placeholderCopy3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Value` |  1  |  2  |  1  |  2  |  3  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
                       j           i

对于 i = 4j = 2Item [i] 大于 Item [j] 。但是对于这种情况,如果我们设置 dp [i] = dp [j] + 1 ,我们将得到 2 ,这是{-1,6}不是我们可以使用 Item 做的最好的{3,4,6} [我] 。所以我们放弃了这个。我们将为我们的策略添加一个条件,即:

 placeholderCopyif Item[i]>Item[j] and dp[i]<dp[j] + 1
    dp[i] := dp[j] + 1

我们增加 Ĵ1 。遵循这个策略,如果我们完成我们的 dp 数组,它将如下所示:

 placeholderCopy3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Value` |  1  |  2  |  1  |  2  |  3  |  3  |  4  |
+-------+-----+-----+-----+-----+-----+-----+-----+
                                         j     i

现在我们将迭代这个数组并找出最大值,这将是 LIS 的长度。我们的伪代码将是:

 placeholderCopyProcedure LISLength(Item):
n := Item.length
dp[] := new Array(n)
for i from 0  to n
    dp[i] := 1
end for
for i from 1 to n
    for j from 0 to i
        if Item[i]>Item[j] and dp[i]<dp[j] + 1
            dp[i] := dp[j] + 1
        end if
    end for
end for
l := -1
for i from 0 to n
    l := max(l, dp[i])
end for
Return l

该算法的时间复杂度为 O(n²),其中 n 是序列的长度。

为了找出原始序列,我们需要向后迭代并将其与我们的长度匹配。程序是:

 placeholderCopyProcedure LIS(Item, dp, maxLength):
i := Item.length
while dp[i] is not equal to maxLength
    i := i - 1
end while
s = new Stack()
s.push(Item[i])
maxLength := maxLength - 1
current := Item[i]
while maxLength is not equal to 0
    i := i-1
    if dp[i] := maxLength and Item[i] < current
        current := Item[i]
        s.push(current)
        maxLength := maxLength - 1
    end if
end while
while s is not empty
    x := s.pop
    Print(s)
end while

该算法的时间复杂度为:O(n)