Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

By madcannibal, history, 6 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 :) Comments (32)
 » i learned LIS from here. it's pretty good :)
•  » » thanks buddy :)
•  » » Is this possible to do binarysearch in an unsorted array?
•  » » » NO, It would be wrong. There is a small possibility that you might get the right answer, but overall it would be just wrong.
 » 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.
•  » » i got this thanks :)
•  » » I think we can also use AVL tree instead of the auxiliary table.
 » 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.
•  » » 15 months ago, # ^ | ← Rev. 2 →   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.
•  » » » hahahahah
•  » » » can you share the implementation please, i need to learn
 » Those slides will help you to understand the algorithm idea. https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf
•  » » this explanation pretty good 10 / 10
•  » » Interesting!
•  » » by far the best.
 » 16 months ago, # | ← Rev. 3 →   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(); 
•  » » But how to retain the LIS? This is fine for calculating its length. But what about the LIS itself?
•  » » » It's not possible with the set method, just use segment tree.
•  » » » » Could you tell me how to retain LIS(sequence itself not the length) using segment trees?
•  » » » » » Do the DP and find longest sequence with end value less than current value at index below us, augment the segment tree to return both max and index, then just step back the indices.
•  » » » » It is possible with set. At each $i$, you should store the previous element's index in the LIS that contains $a_i$. For details see this comment.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   Why not? By just iterating over set, We can get elements, Right? Edit: My bad, Got it.
•  » » » Here it is vector with binary search and finding LIS offlineconst int INF = 1e9; int lis(const vector &a) { int n = a.size(); vector f(n), b(n); /// F[i] is binary search position /// B[i] is unordered LIS int res = 0; for (int i = 0; i < n; ++i) { b[i] = +INF; f[i] = lower_bound(b.begin(), b.begin() + res + 1, a[i]) - b.begin(); res = max(res, f[i] + 1); b[f[i]] = a[i]; } /// res is the size of LIS vector LIS; /// Finding real LIS while (n--) { if (f[n] == res) { LIS.emplace_back(a[n]); --res; } } reverse(all(LIS); return LIS.size(); } 
•  » » » »  vector LIS; /// Finding real LIS while (n--) { if (f[n] == res) { LIS.emplace_back(a[n]); --res; } } if condition should be if (f[n]+1 == res)Rest is correct.^^
•  » » It does not work if there are duplicates in a. e.g a = [1, 2, 3, 4, 1] It will give 3 but correct ans is 4
•  » » » Yes it is, sorry for not writting the notice Nondecreasing Longest Subsequence - With unique#include #include #include using namespace std; int main() { int n; cin >> n; vector a(n); for (int &x : a) cin >> x; set S; set::iterator it; for (int x : a) { S.insert(x); it = S.upper_bound(x); if (it != S.end()) S.erase(x); } cout << S.size(); return 0; }  Nondecreasing Longest Subsequence - With duplicates#include #include #include using namespace std; int main() { int n; cin >> n; vector a(n); for (int &x : a) cin >> x; multiset S; multiset::iterator it; for (int x : a) { S.insert(x); it = S.upper_bound(x); if (it != S.end()) S.erase(it); } cout << S.size(); return 0; }  Strict Increasing Longest Subsequence#include #include #include using namespace std; int main() { int n; cin >> n; vector a(n); for (int &x : a) cin >> x; set S; set::iterator it; for (int x : a) { S.insert(x); it = S.upper_bound(x); if (it != S.end()) S.erase(it); } cout << S.size(); return 0; } 
•  » » » » Found this Implementation with vector
•  » » doesn't work for 1 2 3 4 1 or 0 1 0 3 2 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
 » 9 months ago, # | ← Rev. 3 →   [Based on my understanding of http://lightoj.com/article_show.php?article=1000&language=english&type=pdf]The idea is, for each of the elements we want to know what would be the LIS length if this is the last element in the resulting LIS.Let's say our sequence is [2, 3, 1, 5, 6] and the sequence length array is L[-INF, INF, INF, INF, INF, INF]Let's process the input elements one by one — 2:Starting from 0 index, we need to see where it fits in increasing order. It belongs to the 1th index of L[], therefore, if the LIS ends with this element, our answer is 1. Now, our L[] looks like this — [-INF, 2, INF, INF, INF, INF]3:Again, starting from 0 index, it belongs to index next to 2 which is 2. If our LIS ends with 3, the result would be 2.Now L[] looks like this — [-INF, 2, 3, INF, INF, INF]1:Again we start from 0 index, 1 belongs to first index. We don't have to care about the other elements next to it because we are considering only the LIS ending with 1 which can't be longer than this.Now L[] looks like this — [-INF, 1, 3, INF, INF, INF]1 will give is LIS 1, which is lower than our previous result. So, our LIS is still 2.5:Similarly, after processing 5, L[] looks like this — [-INF, 1, 3, 5, INF, INF]Ans: 36:Similary, after processing 6, L[] looks like this — [-INF, 1, 3, 5, 6, INF]Ans: 4Searching in the L[] can be done using binary search since it is always increasing. The complexity would be NLogK.
 » Can anyone code this stack implementation that also gives the LIS https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf