I found algorithm mentioned in The Hitchhiker’s Guide to the Programming Contests (note: this implementation assumes there are no duplicates in the list):
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;
It's an algorithm to find longest increasing subsequence in O(NlogN). If I try to work it with few test cases, it seems to work. But I still couldn't figure out its correctness logic. Also, it doesn't look so intuitive to me.
Can anyone help me gain insight as to why this algorithm works correctly?
How to determine the longest increasing subsequence using dynamic programming?
Please read my explanation there first. If it is still not clear, read the following:
The algorithm keeps the lowest possible ending number for
LIS
of every length. By keeping the lowest numbers, you can extend theLIS
in a maximal way. I know this is not a proof, but maybe it will be intuitive for you.