#include <bits/stdc++.h>
const int N = 505;
int n, cnt_k;
int a[N], s[N];
int f[N][N][55];
int best[N][55][2];
void init() {
  std::cin >> n >> cnt_k;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
}
void prepare() {
  for (int i = 1; i <= n; i++) {
    s[i] = s[i - 1] + a[i];
  }
}
int sum(int x, int y) { return s[y] - s[x - 1]; }
void work() {
  prepare();
  for (int i = 0; i <= n; i++) {
    for (int k = 0; k <= cnt_k; k++) {
      best[i][k][0] = best[i][k][1] = -1000000000;
    }
  }
  memset(f, -1, sizeof(f));
  best[0][0][0] = best[0][0][1] = 0;
  f[0][0][0] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      for (int k = 1; k <= cnt_k; k++) {
        if (j - 1 >= k - 1) {
          if (k != 1) {
            f[i][j][k] = std::max(best[j - 1][k - 1][0] + sum(j, i),
                                  best[j - 1][k - 1][1] - sum(j, i));
          } else {
            f[i][j][k] = 0;
          }
        }
        if (f[i][j][k] != -1) {
          best[i][k][0] = std::max(best[i][k][0], f[i][j][k] - sum(j, i));
          best[i][k][1] = std::max(best[i][k][1], f[i][j][k] + sum(j, i));
        }
      }
    }
    for (int k = 1; k <= cnt_k; k++) {
      best[i][k][0] = std::max(best[i][k][0], best[i - 1][k][0]);
      best[i][k][1] = std::max(best[i][k][1], best[i - 1][k][1]);
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      ans = std::max(ans, f[i][j][cnt_k]);
    }
  }
  std::cout << ans << std::endl;
}
int main() {
  init();
  work();
  return 0;
}
