#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9, N = 30005, K = 205;
const double eps = 1e-6, phi = acos(-1.0);
long long mod(long long a, long long b) {
  if (a >= b || a < 0) a %= b;
  if (a < 0) a += b;
  return a;
}
long long read() {
  long long x = 0;
  int zf = 1;
  char ch;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') zf = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * zf;
}
void write(long long y) {
  if (y < 0) putchar('-'), y = -y;
  if (y > 9) write(y / 10);
  putchar(y % 10 + '0');
}
int f[N][K][4];
int main() {
  int n = read(), k = read();
  for (register int i = 1; i <= k; i++)
    for (register int j = 0; j <= 3; j++) f[0][i][j] = -INF;
  for (register int i = 1; i <= n; i++) {
    int x = read();
    for (register int j = 1; j <= k; j++) {
      int flag = 2 - (j == 1 || j == k);
      f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j - 1][3]) - flag * x;
      f[i][j][1] = max(f[i - 1][j][1], f[i][j][0]);
      f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][1]) + flag * x;
      f[i][j][3] = max(f[i - 1][j][3], f[i][j][2]);
      if (flag - 1) {
        f[i][j][1] = max(f[i][j][1], f[i - 1][j - 1][1]);
        f[i][j][3] = max(f[i][j][3], f[i - 1][j - 1][3]);
      }
    }
  }
  printf("%d\n", max(f[n][k][1], f[n][k][3]));
}
