#include <bits/stdc++.h>
using namespace std;
int n, k, s[405], m, d[405 * 405], dp[405][405], old[405][405], ib[405 * 405],
    db[405 * 405];
void update(int a[], int x, int y) {
  for (int i = x; i <= m; i += i & -i) a[i] = max(a[i], y);
}
int query(int a[], int x) {
  int ret = -(1 << 29);
  for (int i = x; i; i ^= i & -i) ret = max(ret, a[i]);
  return ret;
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = (1); i <= (n); i++) {
    scanf("%d", &s[i]);
    s[i] += s[i - 1];
  }
  for (int i = (1); i <= (n); i++)
    for (int j = (0); j < (i); j++) d[m++] = s[i] - s[j];
  sort(d, d + m);
  m = unique(d, d + m) - d;
  for (int i = (1); i <= (m); i++) ib[i] = db[i] = -(1 << 29);
  for (int i = (1); i <= (n); i++)
    for (int j = (0); j < (i); j++) dp[i][j] = -(1 << 29);
  for (int i = (1); i <= (n); i++) {
    for (int j = (0); j < (i); j++) {
      int p = lower_bound(d, d + m, s[i] - s[j]) - d;
      update(ib, p + 1, s[j] - s[i]);
      update(db, m - p, s[i] - s[j]);
    }
    for (int j = (i + 1); j <= (n); j++) {
      int p = lower_bound(d, d + m, s[j] - s[i]) - d;
      dp[j][i] =
          max(query(ib, p + 1) + s[j] - s[i], query(db, m - p) + s[i] - s[j]);
    }
  }
  for (int z = (2); z < (k); z++) {
    for (int i = (1); i <= (m); i++) ib[i] = db[i] = -(1 << 29);
    for (int i = (1); i <= (n); i++)
      for (int j = (0); j < (i); j++) {
        old[i][j] = dp[i][j];
        dp[i][j] = -(1 << 29);
      }
    for (int i = (1); i <= (n); i++) {
      for (int j = (0); j < (i); j++) {
        int p = lower_bound(d, d + m, s[i] - s[j]) - d;
        update(ib, p + 1, old[i][j] + s[j] - s[i]);
        update(db, m - p, old[i][j] + s[i] - s[j]);
      }
      for (int j = (i + 1); j <= (n); j++) {
        int p = lower_bound(d, d + m, s[j] - s[i]) - d;
        dp[j][i] =
            max(query(ib, p + 1) + s[j] - s[i], query(db, m - p) + s[i] - s[j]);
      }
    }
  }
  int ans = 0;
  for (int i = (1); i <= (n); i++)
    for (int j = (0); j < (i); j++) ans = max(ans, dp[i][j]);
  printf("%d\n", ans);
  scanf("\n");
}
