#include <bits/stdc++.h>
using namespace std;
int N, K, f[30005][205][2], g[30005][205][2];
int main() {
  int i, j, k, x;
  scanf("%d %d", &N, &K);
  for (i = 1; i <= K; i++)
    for (j = 0; j <= 1; j++) f[0][i][j] = g[0][i][j] = -0x7ffffff;
  for (i = 1; i <= N; i++) {
    scanf("%d", &x);
    for (j = 1; j <= K; j++) {
      int tmp = 2 - (j == 1 || j == K);
      f[i][j][0] = max(f[i - 1][j][0] + tmp * x, g[i - 1][j - 1][1] + tmp * x);
      f[i][j][1] = max(f[i - 1][j][1] - tmp * x, g[i - 1][j - 1][0] - tmp * x);
      g[i][j][0] = max(f[i][j][0], g[i - 1][j][0]);
      g[i][j][1] = max(f[i][j][1], g[i - 1][j][1]);
      if (j > 1 && j < K) {
        g[i][j][0] = max(g[i][j][0], g[i - 1][j - 1][0]);
        g[i][j][1] = max(g[i][j][1], g[i - 1][j - 1][1]);
      }
    }
  }
  printf("%d\n", max(g[N][K][0], g[N][K][1]));
  return 0;
}
