最长递增子序列还原为什么需要祖先数组？最终dp数组为何不是LIS？

你对dp数组的性质理解是完全正确的：

• dp数组严格递增，最终长度和LIS的长度完全一致
• dp[i]的定义是所有长度为i+1的递增子序列的最小末尾元素，因此必然满足dp[i] > dp[i-1]

两者核心的区别是：LIS首先必须是原数组的子序列，要求元素的相对出现顺序和原数组完全一致，但dp数组的元素顺序不满足这个要求。

我们可以举一个简单的反例说明：
原数组为[0, 8, 4, 12, 2]，按照O(nlogn)的规则遍历计算dp数组的过程如下：

• 遍历到0：dp = [0]
• 遍历到8：大于dp末尾元素，追加后dp = [0, 8]
• 遍历到4：二分找到dp中第一个大于等于4的元素8，替换后dp = [0, 4]
• 遍历到12：大于dp末尾元素，追加后dp = [0, 4, 12]
• 遍历到2：二分找到dp中第一个大于等于2的元素4，替换后dp = [0, 2, 12]

最终得到的dp数组是[0, 2, 12]，长度为3，和该数组的LIS长度一致。但观察原数组的元素位置：2的索引是4，12的索引是3，2在原数组中出现晚于12，因此[0, 2, 12]根本不是原数组的子序列，自然不可能是LIS。

出现这个问题的原因是dp数组的修改逻辑包含「替换」操作：我们会把后续遍历到的更小元素替换到dp数组的靠前位置，这个操作只维护了「同长度子序列末尾最小」的性质，完全不保证元素的相对顺序和原数组一致，因此dp数组仅能用来计算LIS长度，不能直接作为LIS本身。如果需要得到真实的LIS，需要额外记录每个元素对应的dp下标，最后从后往前回溯还原顺序。

内容的提问来源于stack exchange，提问作者cat_20