×

# How this algorithm for LIS works ?

 0 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 st; set::iterator it; st.clear();  for(i=0; i

 0 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. :) answered 18 May '16, 13:06 4★arpn 464●5●16 accept rate: 29%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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