#include <bits/stdc++.h>
using namespace std;
const int N_ = 405, K_ = 55;
int N, K, A[50000];
long long S[N_];
long long tn[K_][N_], tp[K_][N_];
long long res = -1;
int main() {
  scanf("%d%d", &N, &K);
  for (int i = 1; i <= N; i++) scanf("%d", A + i), S[i] = S[i - 1] + A[i];
  for (int k = 1; k <= K; k++) {
    for (int i = k; i <= N; i++) tp[k][i] = tn[k][i] = -(long long)1e10;
  }
  {
    long long mn = 0, mx = 0;
    for (int i = 1; i <= N; i++) {
      tp[1][i] = S[i] - mn;
      tn[1][i] = mx - S[i];
      mn = min(mn, S[i]);
      mx = max(mx, S[i]);
    }
  }
  for (int k = 2; k < K; k++) {
    for (int i = k; i <= N; i++) {
      long long t = -(long long)1e18, v = -(long long)1e18;
      for (int p = k; p <= i; p++) {
        t = max(t, tn[k - 1][p - 1]);
        v = max(v, tp[k - 1][p - 1]);
        tp[k][i] = max(t + (S[i] - S[p - 1]) * 2, tp[k][i]);
        tp[k][i] = max(v, tp[k][i]);
        tn[k][i] = max(v + (S[p - 1] - S[i]) * 2, tn[k][i]);
        tn[k][i] = max(t, tn[k][i]);
      }
    }
  }
  for (int i = K; i <= N; i++) {
    for (int p = K - 1; p < i; p++) {
      res = max(
          res, max(tp[K - 1][p] + (S[p] - S[i]), tn[K - 1][p] + (S[i] - S[p])));
    }
  }
  printf("%lld\n", res);
  return 0;
}
