Suppose we have an array which consist of n elements: a1, a2, a3, ..... , an and we have given the value of k which is the count of removed elements from the array. So after removing k elements from the array what is the maximum value of absolute difference of the adjacent elements of the array. Suppose,
n=5 k=3
1 2 5 2 1
then we remove 1,2,2 then the remaining elements of the array will be 5 1 so, ans=abs(5-1)=4 (maximum value which we can get).
what is constraint on ( n and k ) ? can you provide question link ?
For every i from 1 to n, choose the minimum and maximum in the range [i-k-1,i-1] (You can use a segment tree or c++ set or deque for the same) and find the absolute difference of both with a[i]. Now the answer will be the maximum among all such 2*n absolute values Using deque complexity will be just O(n)
Can you explain your solution for the given sample case
You can build an array cointaining only the differences, let's call it v2.
On each of the k steps, you remove the minimum element from v2 ( you are actually removing one of the elements of the original array, v ) and update it's left or right side, depending on which element of v was the optimal removal choice.
Building time complexity of the segment tree is
O(n), update and range minimum query time complexities areO(logn). Picking and changing one of the elements of v isO(1). Total time complexity isO(n + k*log^2 n).I hope I'm not messing anything up, but I think that should be it.