#include <bits/stdc++.h>
using namespace std;
const int Direction[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
const int Nmax = 200010;
int n, k;
long long a[20000], pref[20000];
long long f[60][500][500];
long long diff[500][2];
int main() {
  ios::sync_with_stdio(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pref[i] = pref[i - 1] + a[i];
  };
  for (int i = 0; i <= n; i++) diff[i][0] = diff[i][1] = -2000000000;
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) {
      diff[j][0] = max(diff[j][0], pref[j] - pref[i - 1]);
      diff[j][1] = max(pref[i - 1] - pref[j], diff[j][1]);
    };
  long long answer = 0;
  for (int t = 2; t <= k; t++) {
    for (int i = 1; i <= n; i++)
      for (int j = i; j <= n; j++)
        f[t][i][j] = max(diff[i - 1][0] - pref[j] + pref[i - 1],
                         diff[i - 1][1] - pref[i - 1] + pref[j]);
    for (int i = 0; i < n; i++) diff[i][0] = diff[i][1] = -2000000000;
    for (int i = 1; i <= n; i++)
      for (int j = i; j <= n; j++) {
        diff[j][0] = max(diff[j][0], f[t][i][j] + pref[j] - pref[i - 1]);
        diff[j][1] = max(diff[j][1], f[t][i][j] - pref[j] + pref[i - 1]);
      };
  };
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) answer = max(answer, (long long)f[k][i][j]);
  cout << answer << endl;
  return 0;
}
