algorithm - 为什么在恢复最长递增子序列时需要祖先数组？

Question

我查看了以下描述最长递增子序列算法的网站：https ://www.fyears.org/2016/12/LIS.html

在“如何重建子序列？”一节中，它说“我们应该注意最后的dp不是LIS。”

不知何故，我不明白 dp 不是 LIS 吗？

我们知道 dp 是已排序的，并且它包含的被算法修改的条目与 LIS 的长度一样多。索引 i 处的元素不能等于 i-1 处的元素，因为对于每个索引 dp[i] 包含长度为 i + 1 的所有递增子序列中的最小可能结束值。因此，如果存在长度为 i 的子序列+ 1，这意味着还有一个长度为 i 的子序列，因此必须以较小的值结束，对吗？

标签： algorithmsubsequencelis

Answer 1

LIS is a subsequence (fixed order of elements), but DP array isn't saving elements order. Check on array [2, 3, 1]. DP will be [1, 3] after all iterations, but [1, 3] isn't the subsequence of the initial array.