Nope buddy
Hey @gopalagg , I have tried first problem today by using transitive closure method, I want to know whether this logic works or not? Here is my code UqBH3u - Online Python3 Interpreter & Debugging Tool - Ideone.com
In Question 2, do we actually need sparse table, we can just use sliding window approach with 2 pointers first at ‘i’ then second and ‘i+k’ if we move 1 unit to right in array we add A[i+k+1]*k+max(A[i+k+1], previous max) and subtract A[i]*k+prevmax
In question 2, we can simply use a two-pointer approach where elements from i to j will represent a subarray. For every such subarray, we can calculate the cost in O(log(n)) time by using a multiset to store all the elements from i to j for array B to get the maximum element and using a sum variable to store the sum of elements from i to j of array A. If this cost is less than or equal to maxcost, we can add this to our answer as ans=max(ans,j-i+1) and increase j by 1 and update the multiset and sum. If not, then we would just increment i by 1 and update multiset and sum.
Hello, thanks for sharing.
Did you have two problems only?