#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2010;
const long long inf = 1e9;
int N, K;
long long a[MAXN];
vector<pair<long long, long long> > f[MAXN][MAXN];
bool Check(long long maxD) {
  for (int i = 0; i < (N); i++)
    for (int j = 0; j < (K + 1); j++) f[i][j].clear();
  f[0][0].push_back(make_pair(a[0], a[0]));
  f[0][1].push_back(make_pair(-inf, inf));
  for (int i = 0; i < (N - 1); i++) {
    for (int j = 0; j < (K + 1); j++) {
      if (!(int)(f[i][j]).size()) continue;
      sort(f[i][j].begin(), f[i][j].end());
      f[i][j].push_back(make_pair(inf + inf, 0));
      long long l = f[i][j][0].first, r = f[i][j][0].second;
      for (__typeof(f[i][j].begin()) it = f[i][j].begin(); it != f[i][j].end();
           it++) {
        if (it->first > r) {
          if (a[i + 1] >= l - maxD && a[i + 1] <= r + maxD)
            f[i + 1][j].push_back(make_pair(a[i + 1], a[i + 1]));
          if (j < K)
            f[i + 1][j + 1].push_back(
                make_pair(max(-inf, l - maxD), min(inf, r + maxD)));
          l = it->first;
          r = it->second;
        } else {
          r = max(r, it->second);
        }
      }
    }
  }
  for (int i = 0; i < (K + 1); i++)
    if ((int)(f[N - 1][i]).size()) return true;
  return false;
}
int main() {
  while (cin >> N >> K) {
    for (int i = 0; i < (N); i++) scanf("%I64d", a + i);
    if (N == 1) {
      puts("0");
      continue;
    }
    long long st = 0, ed = 2e9;
    while (st <= ed) {
      long long mid = st + ed >> 1;
      if (Check(mid))
        ed = mid - 1;
      else
        st = mid + 1;
    }
    cout << st << endl;
  }
  return 0;
}
