Problem link : link
code : link
I am considering each element as a maximum element and then determining the size of the subarray in which that element can be maximum. If x is my maximum element and y is my minimum element in the optimal subarray, then we have (x-y)<B which implies that my y should be -> x-B< y <= x . Now I store the elements in a vector of pair where the first element is the element at index i and the second element is the index i. Then I sort it based on the first element. After that, I build a segment tree on the modified index array to get the maximum and minimum index of y which will then determine our ans.
In other words, if v[i] is my maximum element of the optimal subarray I need to find the maximum and minimum index of an element in the entire array which has a value y satisfying v[i]-B< y <=v[i]. For this purpose, I am using a segment tree to store the maximum and minimum index in a range and that range I am finding with the help of lower_bound and upper_bound.
If you look at the code maybe you can understand what I am trying to say.
This is giving wrong answer.
Can someone please help me, whether my approach is wrong or am I doing some implementation mistake.
Sorry for poor explanation of my code .
Please, someone, help me .....
The best advice I can offer you — random test case + brute force to check the correctness of your algo. Come on. Don't be lazy. If you still cannot find a case that breaks your code, I can consider helping you.
There is no need of segment tree or something that, this problem more related to two pointers
I used multiset, and AC this problem
Add to multiset element $$$a[i]$$$ and erase elements from the left while the difference between the biggest and smallest element in array more than $$$b$$$, and the longest subarray with $$$max-min >= b$$$ in current state will be size of this multiset. Time complexity : $$$O(nlog(n))$$$