#include <bits/stdc++.h>
inline int getint() {
  register char ch;
  register bool neg = false;
  while (!isdigit(ch = getchar()))
    if (ch == '-') neg = true;
  register int x = ch ^ '0';
  while (isdigit(ch = getchar())) x = (((x << 2) + x) << 1) + (ch ^ '0');
  return neg ? -x : x;
}
const int _inf = -0x40000000;
const int N = 30001, K = 201;
int a[N];
int f[N][K][4];
int main() {
  int n = getint(), k = getint();
  for (register int i = 1; i <= n; i++) {
    a[i] = getint();
  }
  for (register int j = 1; j <= k; j++) {
    for (register int k = 0; k <= 3; k++) {
      f[0][j][k] = _inf;
    }
  }
  for (register int i = 1; i <= n; i++) {
    for (register int j = 1; j <= k; j++) {
      const int s = a[i] * ((j != 1 && j != k) ? 2 : 1);
      f[i][j][0] = std::max(f[i - 1][j][0], f[i - 1][j - 1][3]) - s;
      f[i][j][1] = std::max(f[i - 1][j][1], f[i][j][0]);
      f[i][j][2] = std::max(f[i - 1][j][2], f[i - 1][j - 1][1]) + s;
      f[i][j][3] = std::max(f[i - 1][j][3], f[i][j][2]);
      if (j != 1 && j != k) {
        f[i][j][1] = std::max(f[i][j][1], f[i - 1][j - 1][1]);
        f[i][j][3] = std::max(f[i][j][3], f[i - 1][j - 1][3]);
      }
    }
  }
  printf("%d\n", std::max(f[n][k][1], f[n][k][3]));
  return 0;
}
