### gautam94's blog

By gautam94, 8 years ago,

I am having trouble understanding the nlogn algorithm for solving the LIS problem. I have implemented the algorithm given here on page number 6. Link to CPP implementation. I think it's only checking the subsequence starting at index 0 so how is this algorithm correct? Or is my implementation wrong? Someone please help prove the correctness of this algorithm. Thanks.

• -1

 » 8 years ago, # |   +9
•  » » 8 years ago, # ^ |   0 OK thanks a lot for your help. I understood your solution and its really O(nlogn), but what about the one posted earlier? What's wrong with the implementation I provided?
•  » » » 8 years ago, # ^ |   +3 I think it should be st.erase(it) instead of st.erase(a[i])
•  » » » » 8 years ago, # ^ |   0 That was a really stupid mistake by me. Again thanks for your help.
•  » » » » » 8 years ago, # ^ |   0 Also, if we are searching for non-decreasing longest sequence then your algorithm will not work correctly.
•  » » 8 years ago, # ^ |   0 The problem of this solutions is tracing. How can we get the result array?
•  » » » 8 years ago, # ^ |   0 this post explains it very well.
 » 8 years ago, # | ← Rev. 3 →   0 vector d; int ans, n; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int x; scanf("%d", &x); vector::iterator it = upper_bound(d.begin(), d.end(), x); if (it == d.end()) d.push_back(x); else *it = x; } printf("LIS = %d", d.size()); return 0; } I think this will be helpful.
•  » » 8 years ago, # ^ |   0 It's non-decreasing subsequence, right? Not increasing one.
•  » » » 8 years ago, # ^ |   0 yeah ur right, this is non-decreasing subsequence. but changing upper_bound to lower_bound fixes that! :)
•  » » 6 years ago, # ^ |   0 For Longest decreasing sub sequence, what changes needed in the code ?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +5 Reverse the list i.e. Input array!
•  » » 6 years ago, # ^ |   0 so helpful code
•  » » 5 years ago, # ^ |   0 I think this is for longest non-decreasing subsequence right? And for LIS, we should use std::lower_bound and replace that element? isn't it? Just for confirmation? Thanks.
•  » » » 3 years ago, # ^ |   +3 Yeah, this is non-decreasing subsequence. And yes, using lower_bound instead of upper_bound would make it increasing.
•  » » 5 years ago, # ^ |   0 set st; set::iterator it; st.clear(); for(i=0; i
 » 8 years ago, # |   0 I have a very short implementation:  int n, a[N], b[N], f[N], answer=0; ... // enter n and a[] from keyboard for (int i=1; i<=n; i++){ f[i]=lower_bound(b+1, b+answer+1, a[i])-b; maximize(answer, f[i]); b[f[i]]=a[i]; } printf("%d\n", answer); If you want to print the LIS:  vector T; int require = answer; for (int i=n; i>=1; i--) if (f[i]==require){ T.push_back(a[i]); require--; } // then print T with reversed order int i=T.size(); while (i--) printf("%d ", T[i]); printf("\n"); 
•  » » 7 years ago, # ^ |   0 is it nlogn solution???
•  » » » 7 years ago, # ^ |   +1 lower_bound/upper_bound works O(log(N))
•  » » » » 6 years ago, # ^ |   0 what is these ?
•  » » 6 years ago, # ^ |   0 would u plz tell me from where i can understand your code more descriptively..
•  » » 5 years ago, # ^ |   0 What does this mean? maximize(answer,f[i]);
•  » » » 5 years ago, # ^ |   0 Why does he code in such a cryptic way...
•  » » » » 5 years ago, # ^ |   0 Same question here :/
•  » » » 5 years ago, # ^ |   0 answer = max(answer, f[i])
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 can you check for 2 5 3 1 6 2 7 it gives 3 and 1 2 7 as output 2 5 6 7 is the right answer
•  » » » » » 3 years ago, # ^ |   0 it gives right answer lenght 4 and " 2 3 6 7 " is the answer
•  » » 3 years ago, # ^ |   0 Thanks man ! . This is much better solution than scrambling the google for "_Nlog(N)_ time LIS with result printing" Anyone having problem reading cryptic code ? HERE is the same code in c++ -
•  » » 2 years ago, # ^ |   0 thank you,,,
 » 6 years ago, # |   0 This can also be achieved with segment trees, though the code will be slightly longer because of the update and query functions.
 » 6 years ago, # |   0 I've learned it from this video https://www.youtube.com/watch?v=S9oUiVYEq7EIt's very well explained. My code: #include int a[10001], t[10001], n, l, i; /** a -> This is the input, is an array of integers t -> Each position have the index of the last item in the ith LIS l -> The last valid position of t n -> Size of input a **/ int ceil(int v) { int init = 0, fin = l; ///Start and end for binary search while(init < fin-1) { int m = (init+fin)/2; if(a[t[m]] >= v) fin = m; else init = m; } if(a[t[init]] >= v) return init; return fin; } void lis() { r[0] = 1; t[0] = 0; l = 0; for(i=1; i a[t[l]]) l++, t[l] = i; else t[ceil(a[i])] = i; } }