#include <bits/stdc++.h>
using namespace std;
int f[30010][210][4];
inline int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= k; i++)
    f[0][i][0] = f[0][i][1] = f[0][i][2] = f[0][i][3] = -1 << 30;
  for (int i = 1; i <= n; i++) {
    int x = gi();
    for (int j = 1; j <= k; j++) {
      int t = (j == 1 || j == k ? 1 : 2);
      f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][2]) - x * t;
      f[i][j][0] = max(f[i - 1][j][0], f[i][j][1]);
      f[i][j][3] = max(f[i - 1][j][3], f[i - 1][j - 1][0]) + x * t;
      f[i][j][2] = max(f[i - 1][j][2], f[i][j][3]);
      if (j != 1 && j != k) {
        f[i][j][0] = max(f[i][j][0], f[i - 1][j - 1][0]);
        f[i][j][2] = max(f[i][j][2], f[i - 1][j - 1][2]);
      }
    }
  }
  cout << max(f[n][k][0], f[n][k][2]);
  return 0;
}
