最長的後續序列
任務是在給定的整數陣列中找到最長子序列的長度，使得子序列的所有元素按升序排序。例如， { 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)。