#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)3e4 + 3;
const int MAXK = (int)203;
const int infint = (int)1e9 + 3;
const long long inf = (long long)1e12;
int n, k, a[MAXN], dp[MAXK][MAXN][3], mx[MAXK][MAXN][6];
void refresh(int j, int i) {
  mx[j][i][0] = max(mx[j][i - 1][0], dp[j][i][1] - a[i]);
  mx[j][i][1] = max(mx[j][i - 1][1], dp[j][i][2] + a[i]);
  mx[j][i][2] = max(mx[j][i - 1][2], dp[j][i][1]);
  mx[j][i][3] = max(mx[j][i - 1][3], dp[j][i][2] + 2 * a[i]);
  mx[j][i][4] = max(mx[j][i - 1][4], dp[j][i][1] - 2 * a[i]);
  mx[j][i][5] = max(mx[j][i - 1][5], dp[j][i][2]);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] += a[i - 1];
  }
  memset(dp, -63, sizeof dp);
  memset(mx, -63, sizeof mx);
  int mn = 0;
  for (int i = 1; i <= n; i++) {
    dp[1][i][0] = 0;
    int cur = a[i] - a[i - 1];
    dp[1][i][1] = max(dp[1][i - 1][1] - cur, -cur);
    dp[1][i][2] = max(dp[1][i - 1][2] + cur, cur);
  }
  for (int i = 1; i <= n; i++) {
    dp[1][i][0] = max(dp[1][i][0], dp[1][i - 1][0]);
    dp[1][i][1] = max(dp[1][i][1], dp[1][i - 1][1]);
    dp[1][i][2] = max(dp[1][i][2], dp[1][i - 1][2]);
    refresh(1, i);
  }
  for (int j = 2; j <= k; j++)
    for (int i = 1; i <= n; i++) {
      dp[j][i][0] = max(dp[j][i - 1][0], max(a[i] + mx[j - 1][i - 1][0],
                                             -a[i] + mx[j - 1][i - 1][1]));
      dp[j][i][1] = max(dp[j][i - 1][1], max(mx[j - 1][i - 1][2],
                                             -2 * a[i] + mx[j - 1][i - 1][3]));
      dp[j][i][2] = max(dp[j][i - 1][2], max(2 * a[i] + mx[j - 1][i - 1][4],
                                             mx[j - 1][i - 1][5]));
      refresh(j, i);
    }
  cout << dp[k][n][0];
}
