By madcannibal, history, 5 years ago,

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 :)

• -1

 » 5 years ago, # |   0 i learned LIS from here. it's pretty good :)
•  » » 5 years ago, # ^ |   -7 thanks buddy :)
 » 5 years ago, # |   +5 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, # ^ |   0 i got this thanks :)
•  » » 5 months ago, # ^ |   0 I think we can also use AVL tree instead of the auxiliary table.
 » 5 years ago, # |   +11 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 →   0 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.
•  » » » 3 weeks ago, # ^ |   -25 hahahahah
 » 5 years ago, # |   0 Those slides will help you to understand the algorithm idea. https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf
•  » » 5 years ago, # ^ |   0 this explanation pretty good 10 / 10
•  » » 7 weeks ago, # ^ |   -21 Interesting!
 » 5 months ago, # | ← Rev. 3 →   0 Yes there is Set implementation#define itr iterator ... typedef set si; ... si S; for (int x : a) { S.insert(x); si::itr it = S.upper_bound(x); if(it != S.end()) S.erase(it); } /// LIS length = S.size(); 
 » 5 months ago, # |   0
 » 4 months ago, # |   +3 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