最长的后续序列
任务是在给定的整数数组中找到最长子序列的长度,使得子序列的所有元素按升序排序。例如, { 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 数组。我们将有两个变量 i 和 j 。最初我将是 1 , j 将是 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 = 1 和 j = 0 , Item [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 = 2 , j = 0 , Item [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 = 2 , j = 1 , Item [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 = 3 , j = 0 , Item [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 = 3 , j = 1 , Item [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 = 3 , j = 2 , Item [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 = 4 且 j = 0 , Item [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 = 4 且 j = 1 , Item [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 = 4 且 j = 2 , Item [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)
。