#include <bits/stdc++.h>
using namespace std;
const int N = 30000 + 10;
int rd() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch ^ 48);
    ch = getchar();
  }
  return x * w;
}
int n, k, a[N], f[2][N][2], s[N], g[N], va[2] = {-1, 1};
int main() {
  n = rd(), k = rd() - 2;
  for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + rd();
  memset(f, -0x3f3f3f, sizeof(f));
  int inf = f[0][0][0], nw = 1, la = 0;
  for (int i = 1, l1 = 0, l2 = 0; i <= n; ++i) {
    f[la][i][0] = l2 - a[i], f[la][i][1] = a[i] - l1;
    l1 = min(l1, a[i]), l2 = max(l2, a[i]);
  }
  while (k--) {
    memset(s, -0x3f3f3f, sizeof(s)), memset(g, -0x3f3f3f, sizeof(g));
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= 1; ++j)
        for (int k = 0; k <= 1; ++k)
          f[nw][i][k] =
              max(f[nw][i][k], g[j << 1 | k] + (va[k] - va[j]) * a[i]);
      for (int j = 0; j <= 1; ++j)
        for (int k = 0; k <= 1; ++k)
          s[j << 1 | k] = max(s[j << 1 | k], f[la][i][j]);
      f[la][i][0] = f[la][i][1] = inf;
      for (int j = 0; j <= 1; ++j)
        for (int k = 0; k <= 1; ++k)
          g[j << 1 | k] =
              max(g[j << 1 | k], s[j << 1 | k] + (va[j] - va[k]) * a[i]);
    }
    nw ^= 1, la ^= 1;
  }
  memset(s, -0x3f3f3f, sizeof(s)), memset(g, -0x3f3f3f, sizeof(g));
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= 1; ++j)
      f[nw][i][j] = max(f[nw][i][j], g[j] + (-va[j]) * a[i]);
    for (int j = 0; j <= 1; ++j)
      s[j] = max(s[j], f[la][i][j]), f[la][i][j] = inf;
    for (int j = 0; j <= 1; ++j) g[j] = max(g[j], s[j] + va[j] * a[i]);
  }
  nw ^= 1, la ^= 1;
  int ans = inf;
  for (int i = 1; i <= n; ++i) ans = max(ans, max(f[la][i][0], f[la][i][1]));
  printf("%d\n", ans);
  return 0;
}
