#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T Abs(const T& x) {
  return x < 0 ? -x : x;
}
template <class T>
inline T Sqr(const T& x) {
  return x * x;
}
const int maxn = 410;
const int maxk = 52;
const int inf = 1000 * 1000 * 1000;
int n, k;
int a[maxn];
int dp[maxn][maxn][maxk];
int mxdp[maxn][maxk];
int mndp[maxn][maxk];
int sum[maxn];
int ss[maxn][maxn];
inline int Get(int l, int r) { return sum[r] - (l > 0 ? sum[l - 1] : 0); }
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> k;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    sum[i] = a[i];
    if (i > 0) {
      sum[i] += sum[i - 1];
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) {
      ss[i][j] = Get(i, j);
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= k; ++j) {
      mxdp[i][j] = -inf;
      mndp[i][j] = -inf;
    }
  }
  memset(dp, -1, sizeof(dp));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= i; ++j) {
      dp[i][j][1] = 0;
    }
  }
  for (int i = 0; i < n; ++i) {
    mxdp[i][1] = dp[i][0][1] + Get(0, i);
    mndp[i][1] = dp[i][0][1] - Get(0, i);
    for (int j = 1; j <= i; ++j) {
      mxdp[i][1] = max(mxdp[i][1], dp[i][j][1] + Get(j, i));
      mndp[i][1] = max(mndp[i][1], dp[i][j][1] - Get(j, i));
    }
  }
  int best = -1;
  for (int kk = 2; kk <= k; ++kk) {
    for (int i = 1; i < n; ++i) {
      for (int j = 1; j <= i; ++j) {
        if (mxdp[j - 1][kk - 1] != -inf) {
          dp[i][j][kk] = mxdp[j - 1][kk - 1] - Get(j, i);
        }
        if (mndp[j - 1][kk - 1] != -inf &&
            mndp[j - 1][kk - 1] + Get(j, i) > dp[i][j][kk]) {
          dp[i][j][kk] = mndp[j - 1][kk - 1] + Get(j, i);
        }
        if (dp[i][j][kk] != -1 &&
            (mxdp[i][kk] == -inf || mxdp[i][kk] < dp[i][j][kk] + Get(j, i))) {
          mxdp[i][kk] = dp[i][j][kk] + Get(j, i);
        }
        if (dp[i][j][kk] != -1 &&
            (mndp[i][kk] == -inf || mndp[i][kk] < dp[i][j][kk] - Get(j, i))) {
          mndp[i][kk] = dp[i][j][kk] - Get(j, i);
        }
        if (kk == k && best < dp[i][j][kk]) {
          best = dp[i][j][kk];
        }
      }
    }
  }
  cout << best << endl;
  return 0;
}
