Greetings.
There is any O(N LOG K)
algorithm for longest not strictly increasing subsequence?
Example for longest not strictly increasing subsequence:
n = 3
a[] = {1, 1, 1}
Normal O(N LOG K)
algorithm will give answer = 1
. (Because it's work strictly increasing)
I need modified algorithm to give answer = 3
.
Thanks in advance.
Oh man, you saved my life.
Thank you very much, you are my hero :D.
you're welcome :) if you replace upper_bound with lower_bound, it gives you the normal lis.
One last question.
How to build the solution?
for each i, I define l[i] = longest nondecreasing subsequence which ends on the ith position of input prv[i] = the index which we update l[i] from.
I modify vector<a[j]> lis to vector<pair<a[j], j>> lis. now you can see that on the ith iteration of the algorithm, we get l[i] = pos, prv[i] = lis[pos — 1].second.
now run a recursive algorithm starting from such index z that l[z] = lis.size() and use prv to build the solution.