#include <bits/stdc++.h>
using namespace std;
int n, k, a;
int PP[30001][201], mPP[30001][201];
int PN[30001][201], mPN[30001][201];
int NP[30001][201], mNP[30001][201];
int NN[30001][201], mNN[30001][201];
int main() {
  ios::sync_with_stdio(0);
  cin >> n >> k;
  memset(PP, 0xc0c0c0c0, sizeof PP);
  memset(mPP, 0xc0c0c0c0, sizeof mPP);
  memset(PN, 0xc0c0c0c0, sizeof PN);
  memset(mPN, 0xc0c0c0c0, sizeof mPN);
  memset(NP, 0xc0c0c0c0, sizeof NP);
  memset(mNP, 0xc0c0c0c0, sizeof mNP);
  memset(NN, 0xc0c0c0c0, sizeof NN);
  memset(mNN, 0xc0c0c0c0, sizeof mNN);
  for (int i = 0; i <= n; ++i) {
    PP[i][0] = mPP[i][0] = 0;
    PN[i][0] = mPN[i][0] = 0;
    NP[i][0] = mNP[i][0] = 0;
    NN[i][0] = mNN[i][0] = 0;
  }
  for (int i = 1; i <= n; ++i) {
    cin >> a;
    for (int j = 1; j <= k; ++j) {
      PP[i][j] = PN[i][j] = NP[i][j] = NN[i][j] = 0;
      if (j > 1) PP[i][j] += a, PN[i][j] += a, NP[i][j] -= a, NN[i][j] -= a;
      if (j < k) PP[i][j] += a, PN[i][j] -= a, NP[i][j] += a, NN[i][j] -= a;
      PP[i][j] += max(PP[i - 1][j], max(mPN[i - 1][j - 1], mNN[i - 1][j - 1]));
      PN[i][j] += max(PN[i - 1][j], max(mPN[i - 1][j - 1], mNN[i - 1][j - 1]));
      NP[i][j] += max(NP[i - 1][j], max(mPP[i - 1][j - 1], mNP[i - 1][j - 1]));
      NN[i][j] += max(NN[i - 1][j], max(mPP[i - 1][j - 1], mNP[i - 1][j - 1]));
      mPP[i][j] = max(mPP[i - 1][j], PP[i][j]);
      mPN[i][j] = max(mPN[i - 1][j], PN[i][j]);
      mNP[i][j] = max(mNP[i - 1][j], NP[i][j]);
      mNN[i][j] = max(mNN[i - 1][j], NN[i][j]);
    }
  }
  int ans = max(max(mPP[n][k], mPN[n][k]), max(mNP[n][k], mNN[n][k]));
  cout << ans << endl;
}
