#include <bits/stdc++.h>
using namespace std;
int N, K, in[30010];
vector<vector<int> > cdp(30010, vector<int>(2));
vector<vector<int> > ndp(30010, vector<int>(2));
int f[2][2];
int main() {
  scanf("%d%d", &N, &K);
  --K;
  for (int i = 0; i < N; ++i) scanf("%d", &in[i]);
  int mins = 0, maxs = 0;
  for (int i = 0; i < N; ++i)
    mins = min(mins, 0) + in[i], maxs = max(maxs, 0) + in[i], cdp[i][0] = maxs,
    cdp[i][1] = -mins;
  for (int p = 1; p < K; ++p) {
    f[0][0] = f[0][1] = -1000000000;
    f[1][0] = f[1][1] = -1000000000;
    ndp[0][0] = ndp[0][1] = -1000000000;
    for (int i = 1; i < N; ++i) {
      f[0][1] -= 2 * in[i];
      f[1][0] += 2 * in[i];
      (f[0][0]) = max((f[0][0]), (cdp[i - 1][0]));
      (f[0][1]) = max((f[0][1]), (cdp[i - 1][0] - 2 * in[i]));
      (f[1][0]) = max((f[1][0]), (cdp[i - 1][1] + 2 * in[i]));
      (f[1][1]) = max((f[1][1]), (cdp[i - 1][1]));
      ndp[i][0] = max(f[0][0], f[1][0]);
      ndp[i][1] = max(f[0][1], f[1][1]);
    }
    cdp.swap(ndp);
    for (int i = 1; i < N; ++i)
      (cdp[i][0]) = max((cdp[i][0]), (cdp[i - 1][0])),
      (cdp[i][1]) = max((cdp[i][1]), (cdp[i - 1][1]));
  }
  int ans = -1000000000;
  mins = maxs = 0;
  for (int i = N - 1; i > 0; --i)
    mins = min(mins, 0) + in[i], maxs = max(maxs, 0) + in[i],
    (ans) = max((ans), (cdp[i - 1][0] - mins)),
    (ans) = max((ans), (cdp[i - 1][1] + maxs));
  printf("%d\n", ans);
  return 0;
}
