#include <bits/stdc++.h>
using namespace std;
const int N = 30005, M = 205;
int n, k, f[N][M][4][2], a[N], ans;
int s;
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  memset(f, 128, sizeof(f));
  for (int i = 1; i <= n; i++) f[i][1][0][0] = -a[i], f[i][1][2][0] = a[i];
  for (int i = 1; i < n; i++)
    for (int j = 1; j <= min(k, i); j++)
      for (int l = 0; l <= 3; l++)
        for (int r = 0; r <= 1; r++)
          if (f[i][j][l][r] != f[0][0][0][0]) {
            int v = f[i][j][l][r];
            s = 0;
            if (l == 0)
              s = -2;
            else if (l == 3)
              s = 2;
            if (j == 1) {
              if (l == 0)
                s = -1;
              else if (l == 2)
                s = 1;
            }
            if (j == k) {
              if (l == 0 || l == 2)
                s = -1;
              else
                s = 1;
            }
            if (!r)
              f[i + 1][j][l][r] = max(f[i + 1][j][l][r], v + s * a[i + 1]);
            f[i + 1][j][l][1] = max(f[i + 1][j][l][1], v);
            for (int w = 0; w <= 1; w++) {
              int t = (w << 1) | ((l & 2) == 0);
              s = 0;
              if (t == 0) s = -2;
              if (t == 3) s = 2;
              if (j + 1 == k) {
                if (t == 0 || t == 2)
                  s = -1;
                else
                  s = 1;
              }
              f[i + 1][j + 1][t][0] =
                  max(f[i + 1][j + 1][t][0], v + s * a[i + 1]);
            }
          }
  for (int i = 0; i <= 3; i++)
    for (int j = 0; j <= 1; j++) ans = max(ans, f[n][k][i][j]);
  printf("%d", ans);
  return 0;
}
