#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2007, INF = 2e9 + 7;
int n, k, a[N], ans;
bool dp1[N][N], dp2[N][N];
bool check(int val) {
  int c = 0;
  memset(dp1, 0, sizeof(dp1));
  for (int i = 1; i <= n; i++) {
    c = max(c, abs(a[i] - a[i - 1]));
    dp1[i][0] = c <= val;
    int jmin = k + 1;
    for (int t = i - 2; t >= 1 && i - 1 - t <= k; t--) {
      if ((abs(a[i] - a[t]) + i - t - 1) / (i - t) > val) continue;
      int l = i - 1 - t, r = min(k, jmin);
      while (l <= r) {
        int mid = l + (r - l) / 2;
        if (dp1[t][mid - (i - 1 - t)])
          r = mid - 1;
        else
          l = mid + 1;
      }
      jmin = min(jmin, l);
    }
    if (jmin <= k) dp1[i][jmin] = true;
    for (int j = 1; j <= k; j++) {
      dp1[i][j] = dp1[i][j] || dp1[i][j - 1] ||
                  (dp1[i - 1][j] && abs(a[i] - a[i - 1]) <= val) || j >= i - 1;
    }
  }
  c = 0;
  for (int i = 1; i <= n; i++) {
    c = max(c, abs(a[i] - a[i - 1]));
    dp2[i][0] = c <= val;
    for (int j = 1; j <= k; j++) {
      dp2[i][j] = dp1[i][j] || dp2[i - 1][j - 1];
    }
  }
  return dp2[n][k];
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  a[0] = a[1];
  int amin = a[1], amax = a[1];
  for (int i = 1; i <= n; i++) {
    amin = min(amin, a[i]);
    amax = max(amax, a[i]);
  }
  int l = 0, r = amax - amin;
  while (l <= r) {
    int mid = l + (r - l) / 2;
    int res = check(mid);
    if (res)
      r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%d\n", l);
}
