#include <bits/stdc++.h>
using namespace std;
int n, K, a[100100], f[30030][205][4][2];
bool vis[30030][205][4][2];
void work() {
  memset(f, -127, sizeof(f));
  for (int i = 1; i <= n; i++) {
    f[i][1][0][0] = -a[i];
    f[i][1][2][0] = a[i];
    vis[i][1][0][0] = 1;
    vis[i][1][2][0] = 1;
  }
  for (int i = 1; i < n; i++)
    for (int j = 1; j <= min(K, i); j++)
      for (int k = 0; k <= 3; k++)
        for (int l = 0; l <= 1; l++) {
          if (!vis[i][j][k][l]) continue;
          int v = f[i][j][k][l], sign = 0;
          if (k == 0) sign = -2;
          if (k == 3) sign = 2;
          if (j == 1) {
            if (k == 0) sign = -1;
            if (k == 2) sign = 1;
          }
          if (j == K) {
            if (k == 0 || k == 2)
              sign = -1;
            else
              sign = 1;
          }
          if (!l) {
            vis[i + 1][j][k][l] = 1;
            f[i + 1][j][k][l] = max(f[i + 1][j][k][l], v + sign * a[i + 1]);
          }
          vis[i + 1][j][k][1] = 1;
          f[i + 1][j][k][1] = max(f[i + 1][j][k][1], v);
          for (int w = 0; w <= 1; w++) {
            int s = (w << 1) | ((k & 2) == 0);
            sign = 0;
            if (s == 0) sign = -2;
            if (s == 3) sign = 2;
            if (j + 1 == K) {
              if (s == 0 || s == 2)
                sign = -1;
              else
                sign = 1;
            }
            vis[i + 1][j + 1][s][0] = 1;
            f[i + 1][j + 1][s][0] =
                max(f[i + 1][j + 1][s][0], v + sign * a[i + 1]);
          }
        }
  int ans = 0;
  for (int i = 0; i <= 3; i++)
    ans = max(ans, max(f[n][K][i][1], f[n][K][i][0]));
  cout << ans;
}
int main() {
  cin >> n >> K;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  work();
}
