#include <bits/stdc++.h>
using std::max;
using std::min;
int getch() {
  static const int len = 1 << 20;
  static char buf[len], *st, *ed;
  if (st == ed) ed = buf + fread(st = buf, 1, len, stdin);
  return st == ed ? EOF : *st++;
}
template <typename T>
void read(T& x) {
  static int c, f;
  x = f = 0, c = getch();
  while (!isdigit(c)) f |= c == '-', c = getch();
  while (isdigit(c)) x = x * 10 + c - '0', c = getch();
  if (f) x = -x;
  return;
}
template <typename T, typename... Args>
void read(T& x, Args&... args) {
  return read(x), read(args...);
}
enum state { top, bot, upper, lower };
const int maxn = 3e4 + 3, maxk = 2e2 + 2;
int n, k, a[maxn];
long long f[maxn][maxk][4];
int main() {
  read(n, k), memset(f, 0x80, sizeof(f)),
      f[0][0][top] = f[0][0][bot] = f[0][0][upper] = f[0][0][lower] = 0;
  for (int i = 1; i <= n; i++)
    read(a[i]),
        f[i][0][top] = f[i][0][bot] = f[i][0][upper] = f[i][0][lower] = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= k; j++)
      if (j != 1 && j != k)
        f[i][j][top] =
            max(f[i - 1][j][top], f[i - 1][j - 1][upper]) + (a[i] << 1),
        f[i][j][bot] =
            max(f[i - 1][j][bot], f[i - 1][j - 1][lower]) - (a[i] << 1),
        f[i][j][upper] =
            max(f[i - 1][j][upper], max(f[i - 1][j - 1][upper], f[i][j][bot])),
        f[i][j][lower] =
            max(f[i - 1][j][lower], max(f[i - 1][j - 1][lower], f[i][j][top]));
      else
        f[i][j][top] = max(f[i - 1][j][top], f[i - 1][j - 1][upper]) + a[i],
        f[i][j][bot] = max(f[i - 1][j][bot], f[i - 1][j - 1][lower]) - a[i],
        f[i][j][upper] = max(f[i - 1][j][upper], f[i][j][bot]),
        f[i][j][lower] = max(f[i - 1][j][lower], f[i][j][top]);
  printf("%lld\n", max(f[n][k][upper], f[n][k][lower]));
  return 0;
}
