#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O2")
using namespace std;
const int N = 30000 + 10, K = 210;
const long long MOD = 1000000000 + 7;
const long long INF = 1000000010;
const long long LOG = 25;
int n, k, a[N], mx[N][K], mx2[N][K], DP[N], lazy, Lazy, lazy2, Lazy2, MX, MX2,
    MXX, MXX2, dp[N][K];
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 0; i < N; i++)
    for (int j = 0; j < K; j++) mx[i][j] = mx2[i][j] = dp[i][j] = -INF;
  mx[0][1] = -INF;
  for (int i = 1; i <= n; i++) {
    DP[i] = max(a[i], DP[i - 1] + a[i]);
    mx[i][1] = max(mx[i - 1][1], DP[i]);
  }
  DP[0] = 0;
  mx2[0][1] = -INF;
  for (int i = 1; i <= n; i++) {
    DP[i] = max(-a[i], DP[i - 1] - a[i]);
    mx2[i][1] = max(mx2[i - 1][1], DP[i]);
  }
  for (int j = 2; j <= k; j++) {
    MX = MX2 = MXX = MXX2 = -INF;
    lazy = Lazy = lazy2 = Lazy2 = 0;
    for (int i = 1; i <= n; i++) {
      lazy += a[i];
      mx[i][j] = max(mx[i - 1][j], mx[i - 1][j - 1]);
      mx2[i][j] = max(mx2[i - 1][j], mx2[i - 1][j - 1]);
      dp[i][j] = dp[i - 1][j];
      dp[i][j] = max(dp[i][j], max(MX2 + lazy, MX - lazy));
      mx2[i][j] = max(mx2[i][j], MXX - 2 * lazy);
      mx[i][j] = max(mx[i][j], MXX2 + 2 * lazy);
      MX = max(MX, mx[i][j - 1] + lazy);
      MX2 = max(MX2, mx2[i][j - 1] - lazy);
      MXX = max(MXX, mx[i][j - 1] + 2 * lazy);
      MXX2 = max(MXX2, mx2[i][j - 1] - 2 * lazy);
    }
  }
  cout << dp[n][k];
  return 0;
}
