如何证明以下算法的正确性

Question

问题是找到任何给定数组的 LIS（最长递增子序列）。 前任。 a[]={10,9,7,8,9}; 长度=3； {7,8,9}

所以在 nlogn 中的一种做法是

1. 对数组进行排序
2. 拿下两者的LCS 结果是 LIS。

现在我知道怎么做了。但是我如何证明它是正确的。这里如何申请MI？

Answer 1

在你的情况下不需要归纳，你必须展示三件事：

• 结果方法捕获递增序列 - 直接来自于它是排序数组的一部分这一事实
• 结果子序列存在于输入数组中 - 直接来自 LCS 的定义（common 子序列）
• 不再有增加的子序列 - 你可以很容易地证明最长的序列必须存在于输入序列（根据定义）和排序数组中，所以它也会被 LCS 分析，因此它不能比 LCS 返回的更长。