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.
We maintain an array $$$E$$$, where $$$E_i$$$ is the smallest number that a LIS of length $$$i$$$ can $$$E$$$ nd with. At the start, $$$E_i = inf$$$ for all $$$1 \leq i \leq N$$$, and $$$E_0 = -inf$$$.
Then, process the numbers of the input array $$$A$$$ from left to right. Let's say we're on $$$A_k$$$. We want to find the last index $$$i$$$ in $$$E$$$ such that $$$E_i < A_k$$$. What this means is that, using the numbers $$$A_0, \cdots, A_{k-1}$$$, we could build a LIS of length $$$i$$$ which ends with $$$E_i$$$, a number smaller than $$$A_k$$$. We can then append $$$A_k$$$ to this LIS, getting a LIS of length $$$i+1$$$ ending with $$$A_k$$$. This means $$$E_{i+1} = min(E_{i+1},A_k)$$$.
This is the only improvement we can make, as we couldn't append $$$A_k$$$ to LIS's represented by $$$E_{i+1}, \cdots, E_N$$$ as their last elements are $$$ \geq A_k$$$, so they wouldn't be LIS after appending $$$A_k$$$, and there is no point appending $$$A_k$$$ to LIS's represented by $$$E_0, \cdots, E_{i-1}$$$ as we already have LIS's longer than them ending in a number smaller than $$$A_k$$$.
In each step, we have for every length $$$i$$$ the smallest number that a LIS of that length can end with, using the numbers we have processed so far. At the end, we have the answer for the whole array $$$A$$$: $$$E_L$$$. If it's $$$inf$$$, there is no LIS of length $$$L$$$ in $$$A$$$.
The step 'find the last index $$$i$$$ in $$$E$$$ such that $$$E_i < A_k$$$' can be done using binary search, as $$$E_i$$$ is non-decreasing. The complexity is $$$O(NlogN)$$$.
Really liked your idea. It's really an amazing solution. Possibly we can now answer the last element of an increasing sequence with any length!