madcannibal's blog

By madcannibal, history, 5 years ago, In English

i wish that anyone explains to me in simple way the algorithm of the Longest Increasing Subsequence in O(nlogn) time , cuz i actually read all online articles about it and found no one explain it well , thanks in advance :)

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i learned LIS from here. it's pretty good :)

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

the trick for the nlogn solution is to maintain, in addition to your dp table, an auxiliary table A so that A[ i ] holds the information "what is the minimum number in the array, such that an increasing subsequence of length i terminates at", it is easy to see that this array will be strictly increasing. Therefore, we can simply binary search the solution of every subproblem and update our array.

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

It is also worth mentioning that you can do LIS in O(n log n) time simply by improving the O(n^2) DP. Everything you need is coordinate compression and a Fenwick tree / interval tree. The code is longer than with the bsearching algorithm, but for many people the idea is simpler because it uses tools they already know.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think it can be done without coordinate compression by processing in increasing order of value and using a segment tree in O(n log n).

    Edit: sorry for necroposting, didn't realise this blog was from 5 years ago.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Yes there is

Set implementation
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Well yeah,there are a lot of articles and finally I found a video which explains the NlogN algorithm with an example step by step and the actual idea/logic behind it.You can refer it : https://youtu.be/nf3YG4CnTbg