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

Правка en2, от aopo, 2021-08-05 11:53:30

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 upperbound 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. Язык Кто Когда Δ Комментарий
en3 Английский aopo 2021-08-05 14:47:23 1 Tiny change: ' the upperbound of a' -> ' the upper_bound of a'
en2 Английский aopo 2021-08-05 11:53:30 41
en1 Английский aopo 2021-08-05 11:40:12 783 Initial revision (published)