#include <bits/stdc++.h>
using namespace std;
long long rdtsc() {
  long long tmp;
  asm("rdtsc" : "=A"(tmp));
  return tmp;
}
inline int myrand() { return abs((rand() << 15) ^ rand()); }
inline int rnd(int x) { return myrand() % x; }
const int INF = (int)1e9 + 1;
const long double EPS = 1e-9;
const int maxn = (int)3e4 + 10;
int a[maxn];
void calcSuf(int n, int *a, int *d) {
  int sum = 0;
  for (int i = 0; i < n; ++i) {
    sum = max(sum, 0) + a[i];
    d[i] = sum;
  }
}
int pref[2][maxn], suf[2][maxn];
const int maxk = 200 + 10;
int d[maxk + 1][4], nd[maxk + 1][4];
bool solve() {
  int n, k;
  if (scanf("%d%d", &n, &k) < 2) return 0;
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  for (int it = 0; it < 2; ++it) {
    calcSuf(n, a, pref[it]);
    for (int i = 0; i < n; ++i) a[i] = -a[i];
  }
  {
    reverse(a, a + n);
    for (int it = 0; it < 2; ++it) {
      calcSuf(n, a, suf[it]);
      reverse(suf[it], suf[it] + n);
      for (int i = 0; i < n; ++i) a[i] = -a[i];
    }
    reverse(a, a + n);
  }
  for (int curk = 1; curk < k; ++curk) {
    for (int type = 0; type < 4; ++type) {
      d[curk][type] = -INF;
    }
  }
  int ans = -INF;
  for (int i = 0; i < n - 1; ++i) {
    {
      if (d[1][0] < pref[0][i]) d[1][0] = pref[0][i];
      if (d[1][1] < pref[1][i]) d[1][1] = pref[1][i];
    }
    for (int curk = 1; curk < k; ++curk)
      for (int type = 0; type < 4; ++type) {
        int cur = d[curk][type];
        if (cur == -INF) continue;
      }
    {
      for (int type = 0; type < 4; ++type) {
        int value = d[k - 1][type];
        if (type & 1)
          value += suf[0][i + 1];
        else
          value += suf[1][i + 1];
        ans = max(ans, value);
      }
    }
    for (int curk = 1; curk < k; ++curk)
      for (int type = 0; type < 4; ++type) nd[curk][type] = -INF;
    for (int curk = 1; curk < k; ++curk) {
      for (int type = 0; type < 4; ++type) {
        if (d[curk][type] == -INF) continue;
        for (int ntype = 0; ntype < 4; ++ntype) {
          if (type < 2 && (ntype != type && (ntype ^ 3) != type)) continue;
          if (type >= 2 && (ntype ^ 3) == type) continue;
          int ncurk = curk + (ntype >= 2 && type != ntype);
          if (ncurk >= k) continue;
          int coef = (ntype < 2) ? 0 : (ntype == 2 ? a[i + 1] : -a[i + 1]);
          coef += coef;
          nd[ncurk][ntype] = max(nd[ncurk][ntype], d[curk][type] + coef);
          if (coef == 0 && ncurk + 1 < k) {
            nd[ncurk + 1][ntype] =
                max(nd[ncurk + 1][ntype], d[curk][type] + coef);
          }
        }
      }
    }
    for (int curk = 1; curk < k; ++curk)
      for (int type = 0; type < 4; ++type) d[curk][type] = nd[curk][type];
  }
  printf("%d\n", ans);
  assert(ans >= 0);
  return 1;
}
int main() {
  srand(rdtsc());
  while (1) {
    if (!solve()) break;
  }
  return 0;
}
