How to solve (NDS — Increasing numbers SPOJ) using LIS?

Revision en3, by aopo, 2021-08-05 14:47:23

Hello connections!

Recently i tried my hands on this problem. I solved it using segment tree and fenwick tree but i don't know how to solve it using LIS concept. It would be very nice if some of you can share your approach for solving this.

Here is what i think regarding this!

We maintain a multiset and go on inserting elements from left to right adding elements one by one , finding the upper_bound of ai and removing it if its exists and then doing ans=max(ans,*st.rbegin()) if the size of my multiset is bigger than l.But this is giving me WA.I don't know where am i going wrong.It would be very helpful if someone can point out my mistake.

Link to Problem


  Rev. Lang. By When Δ Comment
en3 English aopo 2021-08-05 14:47:23 1 Tiny change: ' the upperbound of a' -> ' the upper_bound of a'
en2 English aopo 2021-08-05 11:53:30 41
en1 English aopo 2021-08-05 11:40:12 783 Initial revision (published)