title: Minimize the maximum absolute difference of adjacent elements when at most k elements can changed to any integer
body: <p>We have given an array of integers <code>A</code> with <code>n</code> elements, and an integer <code>k</code>.</p>
  <p>We need to minimize the maximum absolute difference between the adjacent elements, such that at most <code>k</code> elements can be changed to any integer.</p>
  <p>With constraints: <code>n &lt;= 2000</code> and <code>-10^9 &lt;= A[i] &lt;= 10^9</code> for all <code>0 &lt;= i &lt; n</code>. Also, <code>k &lt;= n</code>.</p>
  <p>My approach was to try binary search. I kept lower limit as zero and upper limit as maximum absolute difference of adjacent elements currently in the array.
  Then check if it is possible to make an array having some amount, let's say <code>m = (l + (r - l) / 2)</code>, is possible after changing k elements to have as the maximum absolute difference of adjacent elements.</p>
  <p>But I was not able to check this possibility efficiently? I tried to brute force my way by changing the adjacent elements if the difference is greater than said <code>m</code>. But I am missing something here.
  Can anyone suggest any solutions?</p>