https://www.spoj.com/problems/ONEXLIS/
i have been trying to solve the problem for a long time...but couldnt come up with a proper approach... My approach(ig wrong) : when we consider a sequence to be lis, the elements before the last element must have lds(longest strictly decreasing subsequence) > 1; however im unable to implement the idea; any help would be appreciated.
Auto comment: topic has been updated by Whimsical_HITMAN (previous revision, new revision, compare).
Firstly without loss of generality, we can assume that $$$0 \le a_i \le n - 1$$$, by coordinate compression.
Let's try fixing the one pair that is out of order in the subsequence. Define $$$l_x, r_x$$$ to be the longest increasing sequence ending at index $$$x$$$ and the longest increasing sequence starting from index $$$y$$$ respectively. These values can be computed for all $$$x$$$ using a segment tree in one pass. Then the answer to the problem is $$$\max_{i < j, a[i] > a[j]} l_i + r_j$$$. Iterating over $$$j$$$, this is also doable using a segment tree.
iterating over all j will give tle right?
For every $$$j$$$ you do $$$O(\log n)$$$ work, so it should not.