我在程序竞赛指南中找到了一个算法(注意:此实现假定列表中没有重复项):
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)时间内寻找最长递增子序列的算法。如果我用一些测试案例来验证,它似乎可以工作。但我仍然无法理解其正确性逻辑。而且,对我来说它看起来不那么直观。
有人能帮我理解这个算法为什么正确吗?