#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int N, K;
int A[402], S[402];
int D[52][402][402];
set<pair<int, int> > S1, S2;
void insert_set1(pair<int, int> pn) {
  auto it = S1.lower_bound(make_pair(pn.first + 1, -INF));
  bool ok = true;
  if (it != S1.begin()) {
    --it;
    if (pn.second <= it->second) ok = false;
  }
  if (ok) {
    S1.insert(pn);
    auto it = S1.lower_bound(pn);
    if (it != S1.begin()) {
      --it;
      if (it->first == pn.first) S1.erase(it);
    }
    it = S1.lower_bound(pn);
    ++it;
    while (it != S1.end() && pn.second > it->second) {
      S1.erase(it);
      it = S1.lower_bound(pn);
      ++it;
    }
  }
}
void insert_set2(pair<int, int> pn) {
  auto it = S2.lower_bound(make_pair(pn.first, -INF));
  bool ok = true;
  if (it != S2.end()) {
    if (pn.second <= it->second) ok = false;
  }
  if (ok) {
    S2.insert(pn);
    auto it = S2.lower_bound(pn);
    ++it;
    if (it != S2.end()) {
      if (it->first == pn.first) S2.erase(it);
    }
    while (true) {
      it = S2.lower_bound(pn);
      if (it == S2.begin()) break;
      --it;
      if (pn.second > it->second)
        S2.erase(it);
      else
        break;
    }
  }
}
int main() {
  cin.sync_with_stdio(false);
  cin >> N >> K;
  for (int i = 1; i <= N; ++i) {
    cin >> A[i];
    S[i] = S[i - 1] + A[i];
  }
  memset(D, -1, sizeof(D));
  D[0][0][0] = 0;
  int result = 0;
  for (int i = 1; i <= K; ++i) {
    S1.clear();
    S2.clear();
    for (int j = i; j <= N; ++j) {
      for (int k = i - 1; k <= j - 1; ++k)
        if (D[i - 1][k][j - 1] != -1) {
          insert_set1(make_pair(S[j - 1] - S[k - 1],
                                D[i - 1][k][j - 1] - (S[j - 1] - S[k - 1])));
          insert_set2(make_pair(S[j - 1] - S[k - 1],
                                D[i - 1][k][j - 1] + (S[j - 1] - S[k - 1])));
        }
      for (int k = j; k <= N - (K - i); ++k) {
        int sum = S[k] - S[j - 1];
        auto it = S1.lower_bound(make_pair(sum, -INF));
        if (it != S1.begin()) {
          --it;
          D[i][j][k] = max(D[i][j][k], sum + it->second);
        }
        it = S2.lower_bound(make_pair(sum + 1, -INF));
        if (it != S2.end()) D[i][j][k] = max(D[i][j][k], -sum + it->second);
        if (i == 1) D[i][j][k] = 0;
        if (i == K) result = max(result, D[i][j][k]);
      }
    }
  }
  cout << result << '\n';
}
