#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int S = 0;
  char ch = ' ';
  bool f = 0;
  while (!isdigit(ch)) {
    f |= (ch == '-');
    ch = getchar();
  }
  while (isdigit(ch)) {
    S = (S << 3) + (S << 1) + (ch - '0');
    ch = getchar();
  }
  return (f) ? (-S) : (S);
}
inline void write(int x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x < 10) {
    putchar(x + '0');
    return;
  }
  write(x / 10);
  putchar(x % 10 + '0');
}
const int N = 30005, B = 205;
int n, m, a[N], dp[N][B][4];
inline int cmax(int &x, int y) {
  x = max(x, y);
  return x;
}
int main() {
  int i, j, k, oo;
  n = read();
  m = read();
  for (i = 1; i <= n; i++) a[i] = read();
  memset(dp, -63, sizeof dp);
  for (i = 0; i <= n; i++)
    for (k = 0; k < 4; k++) dp[i][0][k] = 0;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= min(i, m); j++) {
      if (j == 1 || j == m)
        oo = 1;
      else
        oo = 2;
      dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j - 1][3]) - oo * a[i];
      dp[i][j][1] = max(dp[i][j][0], dp[i - 1][j][1]);
      dp[i][j][2] = max(dp[i - 1][j][2], dp[i - 1][j - 1][1]) + oo * a[i];
      dp[i][j][3] = max(dp[i][j][2], dp[i - 1][j][3]);
      if (oo == 2) {
        cmax(dp[i][j][1], dp[i - 1][j - 1][1]);
        cmax(dp[i][j][3], dp[i - 1][j - 1][3]);
      }
    }
  write(max(dp[n][m][1], dp[n][m][3])), putchar('\n');
  return 0;
}
