Modified lis wa

#1

please help with the wa in modified lcs as it is passing the test cases given in question and it seems enough correct code to me.
link to my code -

#2

@mohitbiddu1 hey dp solution will not work here,Please try the problem using fenwick tree(BIT), Think in terms of mapping the numbers and finding the sum for each index using BIT. Expected complexity for each test case will be around n log n

#3

but i think using binary search concept i.e upperbound, we can solve it in o(nlogn) and i have done it in this way.Logic wise it is simple problem ,a slight modification of lis problem which has to be solved in o(nlogn) .

please explain me why can’t we solve it using binarysearch concept.

#4

@mohitbiddu1 hey that approach will give TLE ,you can try this method:
First tu pair banakr sort krle all pairs , next tu simple lis laga de jo second array bani bass…
lis can also be done in onlogn see this:


Also please read about BIT you will definitely get it.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.