最长的后续序列
任务是在给定的整数数组中找到最长子序列的长度，使得子序列的所有元素按升序排序。例如， { 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 。我们的数组看起来像： **** **** **** **** **** **** **** **** **** ****
3 4 -1 0 6 2 3
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Index` | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
+-------+-----+-----+-----+-----+-----+-----+-----+
| `Value` | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+-----+-----+-----+-----+-----+-----+-----+
j i
数组上方的数字代表我们序列的相应元素。我们的策略是：
if Item[i] > Item[j]
dp[i] := dp[j] + 1
这意味着，如果在元件我是比元件更大 Ĵ ，包含元件在 LIS 的长度 Ĵ ，将长度增加 1 ，如果我们包括元件在我它。在我们的例子中，对于 i = 1 和 j = 0 ， Item [i] 大于 Item [j] 。所以 dp [i] = dp [j] + 1 。我们的数组看起来像：
3 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 。
3 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 。
3 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 。
3 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 。
3 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 。
3 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 。
3 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 。
3 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 。
3 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} [我] 。所以我们放弃了这个。我们将为我们的策略添加一个条件，即：
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
我们增加 Ĵ 由 1 。遵循这个策略，如果我们完成我们的 dp 数组，它将如下所示：
3 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 的长度。我们的伪代码将是：
Procedure 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 是序列的长度。
为了找出原始序列，我们需要向后迭代并将其与我们的长度匹配。程序是：
Procedure 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)。