n8118's blog

Longest Increasing Subsequence
By n8118, history, 9 years ago, In English

Can some one explain LIS, a O(nlog(n)) solution clearly as i couldn't find more resources to learn clearly on internet

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

I learned it from this link

It's basic greedy idea is that you declare an array called "position", where the i'th element represent's the smallest number from the sequence that might be the last element in an increasing sub sequence with length i.

e.g: 2, 5, 3, 7, 11,

all increasing sub sequences with length 1:

` 2

5

3

7

11 `

but the algorithm will choose 2 and assign it to index 1 of array position.

all increasing sub sequences with length 2:

` 2 5

2 3

2 7

2 11

5 7

5 11

3 7

3 11 `

we took 2 as the first element in a sub sequence of length 1 so we will discard all sub sequences that starts with 3 and 5

the algorithm will choose 3 as the best element and assign it to index 2 in array position

and so on, for each index in array position, the algorithm will greedly choose the least element not choosen yet to be the last element in a subsequence of length "index"

this is provably true because you will get a better chance to make the last sub sequence as long as possible by taking as small elements as you can in each index.

If the idea wasn't clear, please follow the steps of the algorithm in the above link on a piece of paper and you will get it.

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

short implementation

If you need only length

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Explanation http://stackoverflow.com/a/2631810

→ Reply