#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
int f[31000][210][2][2], g[210][2];
int a[31000], n, K;
void Max(int &x, int y) { x = max(x, y); }
int main() {
  scanf("%d%d", &n, &K);
  for (int i = (1); i <= (n); ++i) scanf("%d", &a[i]);
  memset(f, 250, sizeof(f));
  memset(g, 250, sizeof(g));
  g[0][0] = 0;
  for (int i = (1); i <= (n); ++i) {
    for (int j = (1); j <= (K); ++j) {
      for (int o = (0); o <= (1); ++o)
        for (int p = (0); p <= (1); ++p) {
          int z = g[j - 1][o] + (j == 1 ? 0 : (o == 0 ? -a[i] : a[i])) +
                  (j == K ? 0 : (p == 0 ? a[i] : -a[i]));
          Max(f[i][j][o][p], z);
        }
    }
    for (int j = (1); j <= (K); ++j) {
      for (int o = (0); o <= (1); ++o)
        for (int p = (0); p <= (1); ++p) {
          int z = f[i - 1][j][o][p] + (j == 1 ? 0 : (o == 0 ? -a[i] : a[i])) +
                  (j == K ? 0 : (p == 0 ? a[i] : -a[i]));
          Max(f[i][j][o][p], z);
          Max(g[j][p], f[i][j][o][p]);
        }
    }
  }
  printf("%d\n", max(g[K][0], g[K][1]));
}
