#include <bits/stdc++.h>
using namespace std;
int data[30050], f[4][205][30050];
int Rand() { return (rand() << 15) | rand(); }
int main() {
  int n, m, flag, i, j, best;
  srand((unsigned)time(0));
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) {
    scanf("%d", &data[i]);
  }
  memset(f, 128, sizeof(f));
  f[0][1][1] = data[1];
  f[1][1][1] = -data[1];
  for (i = 2; i <= n; i++) {
    f[0][1][i] = max(data[i], f[0][1][i - 1] + data[i]);
    f[1][1][i] = max(-data[i], f[1][1][i - 1] - data[i]);
  }
  for (i = 2; i <= m; i++) {
    for (j = i; j <= n; j++) {
      f[0][i][j] =
          max(f[0][i][j - 1] + 2 * data[j], f[1][i - 1][j - 1] + 2 * data[j]);
      f[1][i][j] =
          max(f[1][i][j - 1] - 2 * data[j], f[0][i - 1][j - 1] - 2 * data[j]);
      f[2][i][j] = max(f[2][i][j - 1] + data[j], f[1][i - 1][j - 1] + data[j]);
      f[3][i][j] = max(f[3][i][j - 1] - data[j], f[0][i - 1][j - 1] - data[j]);
    }
    for (j = i; j <= n; j++) {
      f[0][i][j] = max(f[0][i][j], max(f[0][i - 1][j - 1], f[0][i][j - 1]));
      f[1][i][j] = max(f[1][i][j], max(f[1][i - 1][j - 1], f[1][i][j - 1]));
    }
  }
  best = 0;
  for (i = m; i <= n; i++) {
    best = max(best, f[2][m][i]);
    best = max(best, f[3][m][i]);
  }
  printf("%d\n", best);
  return 0;
}
