#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:66777216")
using namespace std;
int a, b, c, d, n, m, k;
int mas[402], cs[402];
int dp[52][402][402];
pair<int, int> mn[402][402], mx[402][402];
inline void upd(int &a, int b) {
  if (b > a) a = b;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int _n((n)-1), i(0); i <= _n; i++) {
    scanf("%d", &mas[i]);
    cs[i] = mas[i];
    if (i) cs[i] += cs[i - 1];
  }
  for (int _n((n)-1), r(0); r <= _n; r++) {
    for (int _n((r + 1) - 1), l(0); l <= _n; l++) {
      mn[l][r] = mx[l][r] = make_pair(mas[r], r);
      if (l != r) {
        mn[l][r] = min(mn[l][r], make_pair(mn[l][r - 1].first + mas[r],
                                           mn[l][r - 1].second));
        mx[l][r] = max(mx[l][r], make_pair(mx[l][r - 1].first + mas[r],
                                           mx[l][r - 1].second));
      }
    }
  }
  for (int _n((52) - 1), i(0); i <= _n; i++)
    for (int _n((402) - 1), j(0); j <= _n; j++)
      for (int _n((402) - 1), z(0); z <= _n; z++) dp[i][j][z] = -1000000000;
  for (int _n((n)-1), i(0); i <= _n; i++) {
    for (int _n((i + 1) - 1), j(0); j <= _n; j++) {
      dp[1][i][j] = 0;
    }
  }
  for (int _n((k - 1)), cc(1); cc <= _n; cc++) {
    for (int _n((n)-1), en(0); en <= _n; en++) {
      for (int _n((en + 1) - 1), beg(0); beg <= _n; beg++) {
        int cd = dp[cc][en][beg];
        if (cd <= -1000000000) continue;
        int sum = cs[en];
        if (beg) sum -= cs[beg - 1];
        for (int _n(n - 1), nen(en + 1); nen <= _n; nen++) {
          auto t = mn[en + 1][nen];
          upd(dp[cc + 1][nen][t.second], cd + abs(t.first - sum));
          t = mx[en + 1][nen];
          upd(dp[cc + 1][nen][t.second], cd + abs(t.first - sum));
        }
      }
    }
  }
  int ans = -1000000000;
  for (int _n((n)-1), en(0); en <= _n; en++) {
    for (int _n((en + 1) - 1), beg(0); beg <= _n; beg++) {
      ans = max(ans, dp[k][en][beg]);
    }
  }
  printf("%d\n", ans);
}
