Fenwick tree solution required

#1

Please someone provide solution of this problem with help of fenwick tree ? I am unable to solve this problem. Here solution given is not based on fenwick tree

#2

hello @sachinkumar24051999

Let suppose you are at ith position and maximum weighted subsequence ended at that ith position then what you need is previous maximum weighted subsequence weight ended in 0…i-1 th index, if previous maximum weighted subsequence ending is smallest than the current a[i], you need to update maximum subsequence till now but there may be many indices where the elements are smaller than a[i], so all you have to do is to get the maximum of previously maximum ending subsequence using BIT or you can also use segment tree and make up your answer for current index.

#3

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.