[O(nlogn)]的最长递增子序列算法是如何工作的？

Question

我在程序竞赛指南中找到了一个算法（注意：此实现假定列表中没有重复项）：

set<int> st;
set<int>::iterator it;
st.clear();

for(i=0; i<n; i++) {

  st.insert(array[i]); it=st.find(array[i]);

  it++; if(it!=st.end()) st.erase(it);
}

cout<<st.size()<<endl;

这是一种在O（NlogN）时间内寻找最长递增子序列的算法。如果我用一些测试案例来验证，它似乎可以工作。但我仍然无法理解其正确性逻辑。而且，对我来说它看起来不那么直观。

有人能帮我理解这个算法为什么正确吗？

- aamir

---

请阅读有关“动态规划”和“记忆化”的相关内容，还可以参考以下链接：http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-21-dp-iii-parenthesization-edit-distance-knapsack/。 - noMAD

据我所知，动态规划的解决方案是O(n*n)。 - aamir

动态规划是一种通用的问题解决技术，应用它可以得到具有不同时间复杂度的解决方案，这取决于问题和你如何应用它。例如，动态规划斐波那契数列的时间复杂度是线性的。 - user395760

这就是这个算法的美妙之处。它将给出LIS的正确长度，但集合中的元素不一定是构成LIS的元素！在这种情况下，算法将返回5作为答案，尽管集合中可能有元素{1,2,4,7,9}。 - aamir

最长链的长度等于最小反链覆盖的大小（迪尔沃斯定理）。你可以证明，对于这个偏序集，贪心地找到反链覆盖会产生最优解。 - tmyklebu

Answer 1

描述：对于每个i，当前集合的长度等于最大递增子序列的长度。

证明：使用归纳法的方法：

基本情况：显然成立。

归纳假设：假设我们处理了前 i-1 个元素，并且集合的长度为LIS[i-1]，即前i-1个元素可能具有的最长递增子序列的长度。

归纳步骤：将一个元素 array[i] 插入集合将会有两种情况。

1. A[i] >= set.last() ：在这种情况下，A[i]将成为集合中的最后一个元素，因此 LIS[i] = LIS[i-1]+1。

2. A[i] < set.last() ：在这种情况下，我们将 A[i] 插入集合，并从排序顺序中删除比 A[i] 大的元素。 LIS[i] = LIS[i-1] + 1（添加 A[i]）- 1（删除一个元素> A[i]）。这是正确的。证毕。

为了解释总体情况，将 A[i] 插入集合将要么增加 LIS[i-1] 的值，要么创建它自己的 LIS，该 LIS 将是从第0个位置到第 i 个位置的元素。

- tranquil

Answer 2

如何使用动态规划确定最长递增子序列？

请先阅读我在那里的解释。如果还不清楚，请阅读以下内容：

该算法保留每个长度的LIS的最低可能结束数字。通过保留最低数字，您可以以最大方式扩展LIS。我知道这不是一个证明，但也许对您有直观的帮助。

- Petar Minchev