#include <bits/stdc++.h>
using namespace std;
const char eol = '\n';
int const inf = 1e9;
int n, K;
vector<int> a;
vector<int> ps;
vector<vector<vector<int>>> best;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  cin >> n >> K;
  a = vector<int>(n + 1);
  for (int i = 1; i < (n + 1); ++i) cin >> a[i];
  ps = vector<int>(n + 1);
  for (int i = 1; i < (n + 1); ++i) ps[i] = ps[i - 1] + a[i];
  best = vector<vector<vector<int>>>(
      n + 1, vector<vector<int>>(K + 1, vector<int>(2, -inf)));
  int minp = 0;
  int maxp = 0;
  int mins = inf;
  int maxs = -inf;
  for (int i = 1; i < (n + 1); ++i) {
    mins = min(mins, ps[i] - maxp);
    maxs = max(maxs, ps[i] - minp);
    minp = min(minp, ps[i]);
    maxp = max(maxp, ps[i]);
    best[i][1][0] = -mins;
    best[i][1][1] = maxs;
  }
  int res = -inf;
  for (int k = 1; k < (K); ++k) {
    for (int i = 1; i < (n + 1); ++i) {
      for (int t = 0; t < (2); ++t) {
        int mnp = ps[i];
        int mxp = ps[i];
        int mns = inf;
        int mxs = -inf;
        for (int j = i + 1; j < (n + 1); ++j) {
          mns = min(mns, ps[j] - mxp);
          mxs = max(mxs, ps[j] - mnp);
          mnp = min(mnp, ps[j]);
          mxp = max(mxp, ps[j]);
          if (k + 1 == K) {
            if (t == 0)
              res = max(res, best[i][k][t] + mxs);
            else
              res = max(res, best[i][k][t] - mns);
          } else {
            if (t == 0) {
              best[j][k + 1][0] = max(best[j][k + 1][0], best[i][k][t]);
              best[j][k + 1][1] =
                  max(best[j][k + 1][1], best[i][k][t] + 2 * mxs);
            } else {
              best[j][k + 1][0] =
                  max(best[j][k + 1][0], best[i][k][t] - 2 * mns);
              best[j][k + 1][1] = max(best[j][k + 1][1], best[i][k][t]);
            }
          }
        }
      }
    }
  }
  cout << res << eol;
  return 0;
}
