#include <bits/stdc++.h>
using namespace std;
const int maxn = 30010;
const int maxk = 210;
int n, k;
int a[maxn], s[maxn], f[maxn][maxk][4], g[maxn][maxk][4];
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 i = 0; i <= n; i++)
    for (int j = 0; j <= k; j++)
      for (int t = 0; t < 4; t++) {
        f[i][j][t] = (int)-1e9;
        g[i][j][t] = (int)-1e9;
      }
  int mins = 0, maxs = 0;
  for (int i = 1; i <= n; i++) {
    f[i][1][0] = max(f[i - 1][1][0], -s[i] + maxs);
    f[i][1][1] = max(f[i - 1][1][1], s[i] - mins);
    f[i][1][2] = max(f[i - 1][1][2], -s[i] + maxs);
    f[i][1][3] = max(f[i - 1][1][3], s[i] - mins);
    g[i][1][0] =
        max(g[i - 1][1][0], f[i][1][0] - (1 < k - 1 ? 2 * s[i] : s[i]));
    g[i][1][1] =
        max(g[i - 1][1][1], f[i][1][1] + (1 < k - 1 ? 2 * s[i] : s[i]));
    g[i][1][2] =
        max(g[i - 1][1][2], f[i][1][2] - (1 < k - 1 ? 2 * s[i] : s[i]));
    g[i][1][3] =
        max(g[i - 1][1][3], f[i][1][3] + (1 < k - 1 ? 2 * s[i] : s[i]));
    mins = min(mins, s[i]);
    maxs = max(maxs, s[i]);
  }
  for (int j = 2; j <= k; j++)
    for (int i = j; i <= n; i++) {
      f[i][j][0] = max(g[i - 1][j - 1][1], g[i - 1][j - 1][3]) -
                   (j < k ? 2 * s[i] : s[i]);
      f[i][j][0] = max(f[i - 1][j][0], f[i][j][0]);
      g[i][j][0] =
          max(g[i - 1][j][0], f[i][j][0] - (j < k - 1 ? 2 * s[i] : s[i]));
      f[i][j][1] = max(f[i - 1][j - 1][1], f[i - 1][j - 1][3]);
      f[i][j][1] = max(f[i - 1][j][1], f[i][j][1]);
      g[i][j][1] =
          max(g[i - 1][j][1], f[i][j][1] + (j < k - 1 ? 2 * s[i] : s[i]));
      f[i][j][2] = max(f[i - 1][j - 1][0], f[i - 1][j - 1][2]);
      f[i][j][2] = max(f[i - 1][j][2], f[i][j][2]);
      g[i][j][2] =
          max(g[i - 1][j][2], f[i][j][2] - (j < k - 1 ? 2 * s[i] : s[i]));
      f[i][j][3] = max(g[i - 1][j - 1][0], g[i - 1][j - 1][2]) +
                   (j < k ? 2 * s[i] : s[i]);
      f[i][j][3] = max(f[i - 1][j][3], f[i][j][3]);
      g[i][j][3] =
          max(g[i - 1][j][3], f[i][j][3] + (j < k - 1 ? 2 * s[i] : s[i]));
    }
  printf("%d", max(f[n][k][0], f[n][k][3]));
  return 0;
}
