#include <bits/stdc++.h>
using namespace std;
const int N1[] = {1, -1}, NINF = (int)0x80808080u, MAXN = 30000, MAXK = 200;
long long int dp[MAXN][MAXK + 1][2][2], mdp[MAXN][MAXK + 1][2];
int arr[MAXN], cs[MAXN], n, k;
inline long long int max(long long int a, long long int b) {
  return a > b ? a : b;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
    cs[i] = (i ? cs[i - 1] : 0) + arr[i];
  }
  memset(dp, NINF, sizeof dp);
  memset(mdp, NINF, sizeof mdp);
  mdp[0][0][0] = mdp[0][0][1] = 0;
  for (int p = 0; p < 2; p++)
    for (int q = 0; q < 2; q++) {
      dp[0][1][p][q] = N1[q] * arr[0];
      mdp[0][1][q] = max(mdp[0][1][q], dp[0][1][p][q]);
    }
  for (int i = 1; i < n; i++) {
    mdp[i][0][0] = mdp[i][0][1] = 0;
    mdp[i][1][0] = mdp[i - 1][1][0];
    mdp[i][1][1] = mdp[i - 1][1][1];
    for (int p = 0; p < 2; p++)
      for (int q = 0; q < 2; q++) {
        dp[i][1][p][q] =
            max(dp[i - 1][1][p][q], mdp[i - 1][0][p]) + N1[q] * arr[i];
        mdp[i][1][q] = max(mdp[i][1][q], dp[i][1][p][q]);
      }
    for (int j = 2; j <= k - 1; j++) {
      mdp[i][j][0] = mdp[i - 1][j][0];
      mdp[i][j][1] = mdp[i - 1][j][1];
      for (int p = 0; p < 2; p++)
        for (int q = 0; q < 2; q++) {
          dp[i][j][p][q] = max(dp[i - 1][j][p][q], mdp[i - 1][j - 1][p]) +
                           (N1[q] - N1[p]) * arr[i];
          mdp[i][j][q] = max(mdp[i][j][q], dp[i][j][p][q]);
        }
    }
    mdp[i][k][0] = mdp[i - 1][k][0];
    for (int p = 0; p < 2; p++) {
      dp[i][k][p][0] =
          max(dp[i - 1][k][p][0], mdp[i - 1][k - 1][p]) - N1[p] * arr[i];
      mdp[i][k][0] = max(mdp[i][k][0], dp[i][k][p][0]);
    }
  }
  printf("%I64d\n", mdp[n - 1][k][0]);
  return 0;
}
