我查看了以下描述最長遞增子序列演算法的網站：https ://www.fyears.org/2016/12/LIS.html
在“如何重建子序列？”一節中，它說“我們應該注意最后的dp不是LIS。”
不知何故，我不明白 dp 不是 LIS？
我們知道 dp 是經過排序的，并且它包含與 LIS 長度一樣多的被演算法修改的條目。索引 i 處的元素不能等于 i-1 處的元素，因為對于每個索引 dp[i] 包含所有長度為 i 1 的遞增子序列中的最小可能結束值。因此，如果存在長度為 i 的子序列 1，這意味著還有一個長度為 i 的子序列，因此它必須以較小的值結束，對嗎？
uj5u.com熱心網友回復：
LIS 是一個子序列（元素的固定順序），但 DP 陣列不保存元素順序。檢查陣列 [2, 3, 1]。在所有迭代之后，DP 將是 [1, 3]，但 [1, 3] 不是初始陣列的子序列。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/353916.html
下一篇：對E(startTime,endTime)的排序串列進行二分搜索，以查找與給定時間范圍(t1,t2)匹配的所有E