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

Question

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

所以在 nlogn 中做的一种方法是

1. 对数组进行排序
2. 取LCS的两个Resulting就是LIS。

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

Answer 1

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

• 结果方法捕获增加的序列 - 直接来自它是排序数组的一部分这一事实
• 结果子序列存在于输入数组中 - 直接来自 LCS 的定义（公共子序列）
• 不再有增加的子序列 - 您可以轻松地证明最长序列必须存在于输入序列（根据定义）和排序数组中，因此 LCS 也会对其进行分析，因此它不能比返回的更长由 LCS。