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