为什么在恢复最长递增子序列时需要祖先数组？
Why is an ancestral array needed when recovering longest increasing subsequence?
我查看了以下描述最长递增子序列算法的网站：https://www.fyears.org/2016/12/LIS.html
在“如何重建子序列？”一节中，它说
"我们应该注意最后的 dp 不是 LIS。"
我怎么没看出 dp 不是 LIS？
我们知道 dp 是排序的，它包含与 LIS 的长度一样多的被算法修改的条目。索引 i 处的元素不能等于 i-1 处的元素，因为对于每个索引 dp[i] 包含所有长度为 i + 1 的递增子序列中可能的最小结束值。因此，如果存在长度为 i 的子序列+ 1，这意味着还有一个长度为 i 的子序列，因此它必须以较小的值结束，对吗？
LIS 是一个子序列（元素的固定顺序），但 DP 数组不保存元素顺序。检查数组 [2, 3, 1]。 DP 将在所有迭代后为 [1, 3]，但 [1, 3] 不是初始数组的子序列。
我查看了以下描述最长递增子序列算法的网站：https://www.fyears.org/2016/12/LIS.html
在“如何重建子序列？”一节中，它说 "我们应该注意最后的 dp 不是 LIS。"
我怎么没看出 dp 不是 LIS？
我们知道 dp 是排序的，它包含与 LIS 的长度一样多的被算法修改的条目。索引 i 处的元素不能等于 i-1 处的元素，因为对于每个索引 dp[i] 包含所有长度为 i + 1 的递增子序列中可能的最小结束值。因此，如果存在长度为 i 的子序列+ 1，这意味着还有一个长度为 i 的子序列，因此它必须以较小的值结束，对吗？
LIS 是一个子序列（元素的固定顺序），但 DP 数组不保存元素顺序。检查数组 [2, 3, 1]。 DP 将在所有迭代后为 [1, 3]，但 [1, 3] 不是初始数组的子序列。