java - 最长递增子序列 - 无法理解实际的 LIS 创建

Question

有人可以解释一下 Peter 在文章中给出的最后一个算法吗 How to determine the longest increasing subsequence using dynamic programming?我无法了解实际 LIS 的构造，以及如何构造父数组。请用彼得举的同样的例子来解释。提前致谢。

Answer 1

Peter 示例中最长的递增子序列实际上是“2 3 4 5 8”，长度为 5。

不可能通过查看算法末尾的数组S来获得LIS，并且S不是最长的增加子序列。

如果我们需要构建 LIS，我们将需要存储更多信息并修改所提供的算法。 Peter 在本文后面部分提到存储 parent[i] 并更改 S[i] 以存储索引而不是值。

让我修改他提出的算法并定义 Si 来存储数组 S 和 parent[i] 中数字的索引存储 LIS 中以 array[i] 结尾的前一个数字的索引。使用他的示例:array[] = {2, 6, 3, 4, 1, 2, 9, 5, 8}。请注意，当它们形成最大长度为 1 的 LIS 时，在父数组中使用 -1。

0. S = {} - Initialize S to the empty set
   Si = {}
   parent = {}
1. S = {2} - New largest LIS
   Si = {0}
   parent = {-1}
2. S = {2, 6} - New largest LIS
   Si = {**0**, 1}
   parent = {-1, **0**}
3. S = {2, 3} - Changed 6 to 3
   Si = {**0**, 2}
   parent = {-1, 0, **0**}
4. S = {2, 3, 4} - New largest LIS
   Si = {0, **2**, 3}
   parent = {-1, 0, 0, **2**}
5. S = {1, 3, 4} - Changed 2 to 1
   Si = {4, 2, 3}
   parent = {-1, 0, 0, 2, -1}
6. S = {1, 2, 4} - Changed 3 to 2
   Si = {**4**, 5, 3}
   parent = {-1, 0, 0, 2, -1, **4**}
7. S = {1, 2, 4, 9} - New largest LIS
   Si = {4, 5, **3**, 6}
   parent = {-1, 0, 0, 2, -1, 4, **3**}
8. S = {1, 2, 4, 5} - Changed 9 to 5
   Si = {4, 5, **3**, 7}
   parent = {-1, 0, 0, 2, -1, 4, 3, **3**}
9. S = {1, 2, 4, 5, 8} - New largest LIS
   Si = {4, 5, 3, **7**, 8}
   parent = {-1, 0, 0, 2, -1, 4, 3, 3, 7}

最后我们得到父数组{-1, 0, 0, 2, -1, 4, 3, 3, 7}

1) 通过查看 S，我们知道有一个长度为 5 的 LIS，以索引 8 结尾，值为 8。LIS = { ?, ?, ?, ?, 8 }

2) 我们现在查看索引 8 的父级，parent[8] 是 7，LIS 的前一个成员将位于索引 7 中。这是数字 5。LIS = { ?, ?, ?, 5, 8 }

3) 我们现在查看索引 7 的父级(值 5)，parent[7] 为 3，LIS 的前一个成员将位于索引 3 中。这是数字 4 。LIS = { ?, ?, 4, 5, 8 }

4) 我们现在查看索引 3 的父级(值 4)，parent[3] 为 2，LIS 的前一个成员将位于索引 2 中。这是数字 3 。LIS = { ?, 3, 4, 5, 8 }

5) 我们现在查看索引 2 的父级(值 3)，parent[2] 为 0，LIS 的前一个成员将位于索引 0 中。这是数字 2 。LIS = { 2, 3, 4, 5, 8 }

6) 实际的 LIS 将为 2 3 4 5 8。