#include <bits/stdc++.h>
using namespace std;
template <class T>
T gcd(T x, T y) {
  if (x > y) swap(x, y);
  while (x != 0) {
    T r = y % x;
    y = x;
    x = r;
  }
  return y;
}
template <class T>
int cntbit(T s) {
  return __builtin_popcountll(s);
}
const int inf = (int)(1e9);
const double pi = acos(-1);
const int base = 1;
int n, a[444], s[444], m, g[444][55][2];
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= m; j++) {
      for (int k = 0; k <= 1; k++) g[i][j][k] = -inf;
    }
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) {
      int sum = s[j] - s[i - 1];
      g[j][1][0] = max(g[j][1][0], sum);
      g[j][1][1] = max(g[j][1][1], -sum);
    }
  for (int i = 0; i <= n - 1; i++)
    for (int j = 0; j <= m - 1; j++)
      for (int k = 0; k <= 1; k++)
        if (g[i][j][k] > -inf) {
          g[i + 1][j][k] = max(g[i + 1][j][k], g[i][j][k]);
          for (int i2 = i + 1; i2 <= n; i2++) {
            int sum = s[i2] - s[i], sum2 = sum;
            if (k == 0) sum2 = -sum;
            g[i2][j + 1][0] = max(g[i2][j + 1][0], g[i][j][k] + sum2 + sum);
            g[i2][j + 1][1] = max(g[i2][j + 1][1], g[i][j][k] + sum2 - sum);
          }
        }
  int res = 0;
  for (int i = 1; i <= n - 1; i++)
    for (int j = i + 1; j <= n; j++)
      res = max(res, max(g[i][m - 1][0] - (s[j] - s[i]),
                         g[i][m - 1][1] + s[j] - s[i]));
  cout << res << endl;
  return 0;
}
