4

我发现The Hitchhiker's Guide to the Programming Contests中提到的算法（注意：此实现假定列表中没有重复项）：

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) 中找到最长递增子序列的算法。如果我尝试使用很少的测试用例来处理它，它似乎可以工作。但我仍然无法弄清楚它的正确逻辑。此外，它对我来说看起来并不那么直观。

谁能帮我深入了解为什么这个算法可以正常工作？

4

2 回答 2

4

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

证明：让我们使用归纳法：

基本情况：微不足道。

归纳假设：假设我们已经处理了 i-1 个元素并且集合的长度是 LIS[i-1]，即 LIS 的长度可能与前 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，这将是从第 0 个位置到第 i 个元素位置的元素。

于 2014-05-02T17:03:57.570 回答
2

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

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

该算法为LIS每个长度保持最低可能的结束编号。通过保持最小的数字，您可以LIS以最大的方式扩展。我知道这不是一个证据，但也许它对你来说是直观的。

于 2013-12-14T20:57:19.737 回答