#include <bits/stdc++.h>
using namespace std;
const char lend = '\n';
const int N = 400, M = 51;
int vet[N], n, m, dp[M][N][N], sum[N][N], up[N][N], down[N][N], upaux[N][N][2],
    downaux[N][N][2];
void pre() {
  for (int i = 0; i < n; ++i) {
    up[i][i] = vet[i];
    upaux[i][i][0] = upaux[i][i][1] = i;
    for (int j = i + 1; j < n; ++j) {
      up[i][j] = up[i][j - 1];
      upaux[i][j][0] = upaux[i][j - 1][0];
      upaux[i][j][1] = upaux[i][j - 1][1];
      int now = 0;
      for (int k = j; k >= i; --k) {
        now += vet[k];
        if (now > up[i][j]) {
          up[i][j] = now;
          upaux[i][j][0] = k;
          upaux[i][j][1] = j;
        }
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    down[i][i] = vet[i];
    downaux[i][i][0] = downaux[i][i][1] = i;
    for (int j = i + 1; j < n; ++j) {
      down[i][j] = down[i][j - 1];
      downaux[i][j][0] = downaux[i][j - 1][0];
      downaux[i][j][1] = downaux[i][j - 1][1];
      int now = 0;
      for (int k = j; k >= i; --k) {
        now += vet[k];
        if (now < down[i][j]) {
          down[i][j] = now;
          downaux[i][j][0] = k;
          downaux[i][j][1] = j;
        }
      }
    }
  }
}
const int INF = -1e9;
void solve() {
  --m;
  for (int k = 0; k < m; ++k) {
    for (int i = 0; i < n; ++i)
      for (int j = i; j < n; ++j) dp[k + 1][i][j] = INF;
    for (int i = 0; i < n; ++i) {
      for (int j = i; j < n; ++j) {
        if (dp[k][i][j] == INF) continue;
        for (int x = j + 1; x < n; ++x) {
          int& resa = dp[k + 1][upaux[j + 1][x][0]][upaux[j + 1][x][1]];
          resa = max(resa, dp[k][i][j] + abs(sum[i][j] - up[j + 1][x]));
          int& resb = dp[k + 1][downaux[j + 1][x][0]][downaux[j + 1][x][1]];
          resb = max(resb, dp[k][i][j] + abs(sum[i][j] - down[j + 1][x]));
        }
      }
    }
  }
  int best = INF;
  for (int i = 0; i < n; ++i)
    for (int j = i; j < n; ++j) best = max(best, dp[m][i][j]);
  cout << best << endl;
}
int solve(int a, int b, int c) {
  if (c == m - 1) return 0;
  int& res = dp[a][b][c];
  if (res != -1) return res;
  assert(a <= b);
  res = INF;
  for (int i = b + 1; i < n; ++i) {
    res = max(res, abs(sum[a][b] - up[b + 1][i]) +
                       solve(upaux[b + 1][i][0], upaux[b + 1][i][1], c + 1));
    res =
        max(res, abs(sum[a][b] - down[b + 1][i]) +
                     solve(downaux[b + 1][i][0], downaux[b + 1][i][1], c + 1));
  }
  return res;
}
int main() {
  ios::sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> vet[i];
  for (int i = 0; i < n; ++i)
    for (int j = i; j < n; ++j)
      for (int k = i; k <= j; ++k) sum[i][j] += vet[k];
  pre();
  solve();
}
