#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<int> a;
vector<int> Sum;
inline int get(int l, int r) {
  --r;
  --l;
  int res = 0;
  if (r >= 0) res += Sum[r];
  if (l >= 0) res -= Sum[l];
  return res;
}
const int MAXN = 409;
const int MAXK = 51;
vector<int> DP[MAXN][MAXK];
bool ready[MAXN][MAXK];
const vector<int>& solve(int R, int k) {
  if (k == 1) {
    if (!ready[R][k]) {
      DP[R][k] = vector<int>(R, 0);
      ready[R][k] = true;
    }
    return DP[R][k];
  }
  if (!ready[R][k]) {
    auto& res = DP[R][k];
    ready[R][k] = true;
    res = vector<int>(R, -1e9);
    int maxPlus = -1e9;
    int maxMinus = -1e9;
    for (int nR = R; nR <= n; ++nR) {
      const vector<int>& nS = solve(nR, k - 1);
      for (int L = R; L < nR; ++L) {
        maxPlus = max(maxPlus, nS[L] + get(L, nR));
        maxMinus = max(maxMinus, nS[L] - get(L, nR));
      }
    }
    for (int L = 0; L < R; ++L) {
      res[L] = max(maxPlus - get(L, R), maxMinus + get(L, R));
    }
  }
  return DP[R][k];
}
int main() {
  cin >> n >> k;
  a.resize(n);
  Sum.assign(n + 1, 0);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    Sum[i] += a[i];
    if (i) {
      Sum[i] += Sum[i - 1];
    }
  }
  int maxAns = 0;
  for (int i = 1; i <= n; ++i) {
    vector<int> ans = solve(i, k);
    for (int j = 0; j < i; ++j) {
      maxAns = max(ans[j], maxAns);
    }
  }
  cout << maxAns << endl;
  return 0;
}
