#include <bits/stdc++.h>
using namespace std;
int i, j, k, n, m, u;
int a[410], f[410], g[410], h[410], w[410];
int main() {
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] += a[i - 1];
  for (i = 0; i <= n; i++) f[i] = g[i] = -100000000;
  for (i = 1; i <= n; i++)
    for (j = i; j <= n; j++) {
      int zhi = a[j] - a[i - 1];
      f[j] = max(f[j], -zhi);
      g[j] = max(g[j], zhi);
    }
  for (i = 2; i <= m; i++) {
    int an = -100000000;
    for (j = 0; j <= n; j++) h[j] = w[j] = -100000000;
    for (j = 0; j <= n; j++)
      for (k = j + 1; k <= n; k++)
        for (u = k; u <= n; u++) {
          int zhi = a[u] - a[k - 1];
          an = max(an, f[j] + zhi);
          an = max(an, g[j] - zhi);
          h[u] = max(h[u], f[j] + zhi - zhi);
          h[u] = max(h[u], g[j] - zhi - zhi);
          w[u] = max(w[u], f[j] + zhi + zhi);
          w[u] = max(w[u], g[j] - zhi + zhi);
        }
    for (j = 0; j <= n; j++) f[j] = h[j], g[j] = w[j];
    if (i == m) printf("%d\n", an);
  }
  return 0;
}
