#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
const int INF = 1000 * 1000 * 1000;
int best_hi[410][53];
int best_lo[410][53];
int n, k;
int S[410];
int res;
int main() {
  scanf("%d %d", &n, &k);
  --k;
  for (int i = (0); i < (n); ++i) scanf("%d", &S[i]);
  for (int r = (0); r < (k + 1); ++r) best_hi[0][r] = best_lo[0][r] = -INF;
  for (int i = (1); i < (n + 1); ++i) {
    for (int r = (0); r < (k + 1); ++r) best_hi[i][r] = best_lo[i][r] = -INF;
    int sum = 0;
    for (int fst = (i - 1); fst > (-1); --fst) {
      sum += S[fst];
      best_hi[i][0] = max(best_hi[i][0], sum);
      best_lo[i][0] = max(best_lo[i][0], -sum);
      for (int j = (0); j < (fst + 1); ++j)
        for (int r = (0); r < (k); ++r) {
          best_hi[i][r + 1] = max(best_hi[i][r + 1], best_lo[j][r] + 2 * sum);
          best_hi[i][r + 1] = max(best_hi[i][r + 1], best_hi[j][r]);
          if (r + 1 == k) res = max(res, best_lo[j][r] + sum);
          best_lo[i][r + 1] = max(best_lo[i][r + 1], best_hi[j][r] - 2 * sum);
          best_lo[i][r + 1] = max(best_lo[i][r + 1], best_lo[j][r]);
          if (r + 1 == k) res = max(res, best_hi[j][r] - sum);
        }
    }
  }
  printf("%d\n", res);
  return 0;
}
