#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, M = 205;
int n, m, a[N], qzh[N];
int dp[N][M][4];
int main() {
  int i, j;
  n = read();
  m = read();
  for (i = 1; i <= n; i++) {
    a[i] = read();
    qzh[i] = qzh[i - 1] + a[i];
  }
  memset(dp, -63, sizeof dp);
  for (i = 0; i <= n; i++)
    for (j = 0; j <= 3; j++) dp[i][0][j] = 0;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= min(m, i); j++) {
      int oo = 1 + ((j != 1) && (j != m));
      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 - 1][j][1], dp[i][j][0]);
      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 - 1][j][3], dp[i][j][2]);
      if (oo == 2) {
        dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - 1][1]);
        dp[i][j][3] = max(dp[i][j][3], dp[i - 1][j - 1][3]);
      }
    }
  write(max(dp[n][m][1], dp[n][m][3])), putchar('\n');
  return 0;
}
