#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n, k, x[N], d[55][N][N], sm1[N], sm2[N];
int main() {
  int i, j, l;
  cin >> n >> k;
  for (i = 1; i <= n; ++i) {
    cin >> x[i];
    x[i] += x[i - 1];
  }
  for (i = 2; i <= k; ++i) {
    for (j = 0; j < N; ++j)
      for (l = 0; l < N; ++l) d[i][j][l] = -1000000000;
    memset(sm1, 0, sizeof(sm1));
    memset(sm2, 0, sizeof(sm2));
    sm1[0] = sm2[0] = -100000000;
    for (j = 1; j <= n; ++j) {
      sm1[j] = sm1[j - 1];
      sm2[j] = sm2[j - 1];
      for (l = 1; l <= j; ++l) {
        sm1[j] = max(sm1[j], x[j] - x[l - 1] + d[i - 1][l][j]);
        sm2[j] = max(sm2[j], -x[j] + x[l - 1] + d[i - 1][l][j]);
      }
    }
    for (j = 1; j <= n; ++j) {
      for (l = 1; l <= j; ++l)
        d[i][l][j] =
            max(sm1[l - 1] - (x[j] - x[l - 1]), sm2[l - 1] + (x[j] - x[l - 1]));
    }
  }
  int rez = 0;
  for (i = 1; i <= n; ++i)
    for (j = i; j <= n; ++j) rez = max(rez, d[k][i][j]);
  cout << rez;
  return 0;
}
