最长递增子序列[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）中最长递增子序列的算法。如果我尝试在很少的测试用例中使用它，它似乎是有效的。但我仍然搞不清楚它的正确性逻辑。此外，在我看来，它并不那么直观。

有人能帮助我了解为什么这个算法能正确工作吗？

Answer 1

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

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

基本情况：基本正确。

归纳假设：假设我们已经处理了i-1个元素，并且集合的长度是LIS[i-1]，即第一个i-1元素可能的LIS的长度。

归纳步骤：在集合中插入元素数组[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个元素的位置的元素。

Answer 2

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

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

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