#include <bits/stdc++.h>
const int INF = 0x3f3f3f3f;
int n, m;
int f[55][405][405], s[405];
void DP() {
  int i, j, k, mx, my, ans = 0;
  memset(f, 0, sizeof(f));
  for (i = 1, s[0] = 0; i <= n; i++) {
    scanf("%d", &s[i]);
    s[i] += s[i - 1];
  }
  for (k = 2; k <= m; k++) {
    mx = my = -INF;
    for (i = 1; i <= n; i++) {
      for (j = i; j <= n; j++)
        f[k][i][j] = mx + s[j] - s[i - 1] > my - (s[j] - s[i - 1])
                         ? mx + s[j] - s[i - 1]
                         : my - (s[j] - s[i - 1]);
      for (j = 1; j <= i; j++) {
        mx = mx > f[k - 1][j][i] - (s[i] - s[j - 1])
                 ? mx
                 : f[k - 1][j][i] - (s[i] - s[j - 1]);
        my = my > f[k - 1][j][i] + (s[i] - s[j - 1])
                 ? my
                 : f[k - 1][j][i] + (s[i] - s[j - 1]);
      }
    }
  }
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) ans = ans > f[m][i][j] ? ans : f[m][i][j];
  printf("%d\n", ans);
}
int main() {
  while (~scanf("%d%d", &n, &m)) DP();
  return 0;
}
