#include <bits/stdc++.h>
using namespace std;
const int MAXN = 33333;
const int MAXK = 221;
const long long INF = 1e18;
int n, K, a[MAXN];
long long sum[MAXN], f[MAXN][MAXK], g[MAXN][MAXK];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> K;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    sum[i] = a[i] + sum[i - 1];
  }
  long long mx = 0, mn = 0;
  f[0][1] = g[0][1] = -INF;
  for (int i = 1; i <= n; ++i) {
    f[i][1] = max(f[i - 1][1], sum[i] - mn);
    g[i][1] = max(g[i - 1][1], mx - sum[i]);
    mx = max(sum[i], mx);
    mn = min(sum[i], mn);
  }
  long long ans = -INF;
  for (int j = 2; j <= K; ++j) {
    long long mxf = f[j - 1][j - 1], mxg = g[j - 1][j - 1];
    long long mxff = f[j - 1][j - 1] + 2 * sum[j - 1];
    long long mxgg = g[j - 1][j - 1] - 2 * sum[j - 1];
    long long mxfff = f[j - 1][j - 1] + sum[j - 1];
    long long mxggg = g[j - 1][j - 1] - sum[j - 1];
    f[j - 1][j] = g[j - 1][j] = -INF;
    for (int i = j; i <= n; ++i) {
      f[i][j] = max(f[i - 1][j], mxgg + 2LL * sum[i]);
      f[i][j] = max(f[i][j], mxf);
      g[i][j] = max(g[i - 1][j], mxff - 2LL * sum[i]);
      g[i][j] = max(g[i][j], mxg);
      if (j == K) {
        ans = max(ans, mxfff - sum[i]);
        ans = max(ans, mxggg + sum[i]);
      }
      mxf = max(f[i][j - 1], mxf);
      mxg = max(g[i][j - 1], mxg);
      mxff = max(f[i][j - 1] + 2 * sum[i], mxff);
      mxgg = max(g[i][j - 1] - 2 * sum[i], mxgg);
      mxfff = max(f[i][j - 1] + sum[i], mxfff);
      mxggg = max(g[i][j - 1] - sum[i], mxggg);
    }
  }
  cout << ans << endl;
}
