#include <bits/stdc++.h>
using namespace std;
const int maxn = 30010;
const int inf = 1e9;
int a[maxn];
int sum[maxn];
int n, k;
int dp[maxn][202][2], mx[maxn][202][2];
void up(int &x, int y) { x = max(x, y); }
int coe[2];
int main() {
  coe[0] = -1;
  coe[1] = 1;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    sum[i] = sum[i - 1] + a[i];
  }
  memset(dp, 0xaf, sizeof dp);
  for (int i = 1; i <= n; i++) {
    dp[i][1][0] = dp[i - 1][1][0];
    dp[i][1][1] = dp[i - 1][1][1];
    for (int l = 1; l <= i; l++) {
      int s = (sum[i] - sum[l - 1]);
      up(dp[i][1][0], -s);
      up(dp[i][1][1], s);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 2; j < k; j++) {
      dp[i][j][0] = dp[i - 1][j][0];
      dp[i][j][1] = dp[i - 1][j][1];
      for (int l = 1; l <= i; l++) {
        int s = (sum[i] - sum[l - 1]);
        up(dp[i][j][0], dp[l - 1][j - 1][0] + s - s);
        up(dp[i][j][0], dp[l - 1][j - 1][1] - s - s);
        up(dp[i][j][1], dp[l - 1][j - 1][0] + s + s);
        up(dp[i][j][1], dp[l - 1][j - 1][1] - s + s);
      }
    }
  }
  if (k > 1) {
    for (int i = 1; i <= n; i++) {
      dp[i][k][0] = dp[i - 1][k][0];
      dp[i][k][1] = dp[i - 1][k][1];
      for (int l = 1; l <= i; l++) {
        int s = (sum[i] - sum[l - 1]);
        up(dp[i][k][0], dp[l - 1][k - 1][0] + s);
        up(dp[i][k][0], dp[l - 1][k - 1][1] - s);
        up(dp[i][k][1], dp[l - 1][k - 1][0] + s);
        up(dp[i][k][1], dp[l - 1][k - 1][1] - s);
      }
    }
  }
  int ans = -inf;
  ans = max(dp[n][k][0], dp[n][k][1]);
  cout << ans << endl;
  return 0;
}
