#include <bits/stdc++.h>
using namespace std;
int n, k, f[30010][210][4];
int main() {
  scanf("%d%d", &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] = -0x3f3f3f3f;
  for (int i = 1; i <= n; i++) {
    int x, tmp;
    scanf("%d", &x);
    for (int j = 1; j <= k; j++) {
      if (j == 1 || j == k)
        tmp = 1;
      else
        tmp = 2;
      f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j - 1][3]) - tmp * x;
      f[i][j][1] = max(f[i - 1][j][1], f[i][j][0]);
      f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][1]) + tmp * x;
      f[i][j][3] = max(f[i - 1][j][3], f[i][j][2]);
      if (tmp == 2) {
        f[i][j][1] = max(f[i][j][1], f[i - 1][j - 1][1]);
        f[i][j][3] = max(f[i][j][3], f[i - 1][j - 1][3]);
      }
    }
  }
  printf("%d\n", max(f[n][k][1], f[n][k][3]));
  return 0;
}
