You are not logged in. Please login at www.codechef.com to post your questions!

×

How this algorithm for LIS works ?

This is the O(n*lg(n)) solution for Longest Increasing subsequence taken from The Hitchhiker’s Guide to the Programming Contests (note: this implementation assumes there are no duplicates in the list):

enter code here
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;

I am not able to understand why this algorithm works? Can anybody help me out?

asked 18 May '16, 09:15

sandeep9's gravatar image

3★sandeep9
4782827
accept rate: 4%

edited 18 May '16, 09:17


See basically,in set all the elements will be sorted(increasing order) and no duplicates will be allowed. Now we should start with an example,shall we?
basically we're going to check that after insertion whether the element is inserted in the last position or not. If yes,then we can continue with this number,else we'll erase it.

let's take the example - 1 3 4 2 5
For the iteration 1: set: 1(1 in Last)
For the iteration 2: set: 1 3(3 in Last)
For the iteration 3: set: 1 3 4 (4 in last)
For the iteration 4: set: 1 2 3 4(2 in 2nd,so we'll remove 2,so the new set 1 3 4)
For the iteration 5: set: 1 3 4 5(5 in last)

And voilà,we just got our solution :D. Print the size of the set and that is the correct answer.
Feel free to ask me,if you've any doubts. :)

link

answered 18 May '16, 13:06

arpn's gravatar image

4★arpn
464516
accept rate: 29%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,167

question asked: 18 May '16, 09:15

question was seen: 576 times

last updated: 18 May '16, 13:06