#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 4, K = 204;
int n, k, a[N];
int F[N][K][2], G[N][K][2];
void sol() {
  for (int j = 1; j <= k; ++j) {
    F[0][j][0] = F[0][j][1] = G[0][j][0] = G[0][j][1] = -1e9;
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= k; ++j) {
      int Mul = (j == 1 || j == k) ? 1 : 2;
      F[i][j][0] =
          max(F[i - 1][j][0] + Mul * a[i], G[i - 1][j - 1][1] + Mul * a[i]);
      F[i][j][1] =
          max(F[i - 1][j][1] - Mul * a[i], G[i - 1][j - 1][0] - Mul * a[i]);
      G[i][j][0] = max(G[i - 1][j][0], F[i][j][0]);
      G[i][j][1] = max(G[i - 1][j][1], F[i][j][1]);
      if (j > 1 && j < k) {
        G[i][j][0] = max(G[i][j][0], G[i - 1][j - 1][0]);
        G[i][j][1] = max(G[i][j][1], G[i - 1][j - 1][1]);
      }
    }
  cout << max(G[n][k][0], G[n][k][1]);
}
int 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];
  sol();
  return 0;
}
