#include <bits/stdc++.h>
using namespace std;
const int N = 30000 + 10;
const int K = 200 + 10;
const int INF = 1000000000 + 10;
const int MOD = 1e9 + 7;
int n, k;
int a[N];
int s[N];
int f[K][N][2][2][2];
bool vis[K][N][2][2][2];
int sign(int x) {
  if (x == 0) return -1;
  return 1;
}
void update(int i, int j, int fi, int fj, int c, int x) {
  if (!vis[i][j][fi][fj][c]) {
    f[i][j][fi][fj][c] = x;
    vis[i][j][fi][fj][c] = true;
  }
  f[i][j][fi][fj][c] = max(f[i][j][fi][fj][c], x);
}
void solve() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    s[i] = s[i - 1] + a[i];
  }
  vis[0][0][0][0][0] = true;
  vis[0][0][0][1][0] = true;
  int value;
  for (int i = 0; i < k; ++i) {
    for (int j = 0; j <= n; ++j) {
      for (int fi = 0; fi < 2; ++fi) {
        for (int fj = 0; fj < 2; ++fj) {
          if (vis[i][j][fi][fj][0]) {
            value = f[i][j][fi][fj][0];
            if (j < n) {
              update(i, j + 1, fi, fj, 0, value);
              if (i == 0) {
                update(i, j + 1, fi, fj, 1, value - sign(fj) * s[j]);
              } else if (i == k - 1) {
                update(i, j + 1, fi, fj, 1, value + sign(fi) * s[j]);
              } else {
                update(i, j + 1, fi, fj, 1,
                       value + sign(fi) * s[j] - sign(fj) * s[j]);
              }
            }
          }
          if (vis[i][j][fi][fj][1]) {
            value = f[i][j][fi][fj][1];
            if (j < n) {
              update(i, j + 1, fi, fj, 1, value);
            }
            if (i == 0) {
              update(i + 1, j, fj, 0, 0, value + sign(fj) * s[j]);
              update(i + 1, j, fj, 1, 0, value + sign(fj) * s[j]);
            } else if (i == k - 1) {
              update(i + 1, j, fj, 0, 0, value - sign(fi) * s[j]);
              update(i + 1, j, fj, 1, 0, value - sign(fi) * s[j]);
            } else {
              update(i + 1, j, fj, 0, 0,
                     value - sign(fi) * s[j] + sign(fj) * s[j]);
              update(i + 1, j, fj, 1, 0,
                     value - sign(fi) * s[j] + sign(fj) * s[j]);
            }
          }
        }
      }
    }
  }
  int ret = -INF;
  for (int j = 0; j <= n; ++j) {
    for (int fi = 0; fi < 2; ++fi) {
      for (int fj = 0; fj < 2; ++fj) {
        if (vis[k][j][fi][fj][0]) {
          ret = max(ret, f[k][j][fi][fj][0]);
        }
      }
    }
  }
  cout << ret << endl;
}
int main() {
  solve();
  return 0;
}
