有人可以解释一下 Peter 在文章中给出的最后一个算法吗 How to determine the longest increasing subsequence using dynamic programming? 我无法了解实际 LIS 的构造,以及如何构造父数组。 请用彼得举的同样的例子来解释。 提前致谢。
最佳答案
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
。
关于java - 最长递增子序列 - 无法理解实际的 LIS 创建,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25608857/