deepak_097's blog

Maximum sum of absolute difference b/w adjacent elements after removing k elements from the array.
By deepak_097, history, 5 years ago, In English

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).

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is constraint on ( n and k ) ? can you provide question link ?

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

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)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your solution for the given sample case

    → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

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 are O(logn). Picking and changing one of the elements of v is O(1). Total time complexity is O(n + k*log^2 n).

I hope I'm not messing anything up, but I think that should be it.

→ Reply