#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
double pi = acos((double)-1);
const int MOD = 1000000007;
const int INF = 1000000000;
const double EPS = 1e-9;
const long long LLONG_INF = 9223372036854775807LL;
const int MAXN = 30000 + 10;
int f[MAXN][210][2][2];
int g[MAXN][210][2][2];
int get_f(vector<int>&, int, int, int, int);
int get_g(vector<int>&, int, int, int, int);
int n, k;
int get_g(vector<int>& a, int i, int j, int c1, int c2) {
  if (i == n || j == k) return 0;
  if (g[i][j][c1][c2] == -INF) {
    int f1 = get_f(a, i, j + 1, c2, 0);
    int f2 = get_f(a, i, j + 1, c2, 1);
    int best_empty = max(f1, f2);
    int f3 = -INF;
    if (k - j <= n - i) {
      int d = -(j == 0 ? 0 : (c1 == 1 ? 1 : -1)) * a[i] +
              (j == k - 1 ? 0 : (c2 == 1 ? 1 : -1)) * a[i];
      f3 = d + get_g(a, i + 1, j, c1, c2);
    }
    g[i][j][c1][c2] = max(best_empty, f3);
  }
  return g[i][j][c1][c2];
}
int get_f(vector<int>& a, int i, int j, int c1, int c2) {
  if (i == n) return -INF;
  if (j == k) return 0;
  if (k - j > n - i) return -INF;
  if (f[i][j][c1][c2] == -INF) {
    int d = -(j == 0 ? 0 : (c1 == 1 ? 1 : -1)) * a[i] +
            (j == k - 1 ? 0 : (c2 == 1 ? 1 : -1)) * a[i];
    int f1 = get_f(a, i + 1, j, c1, c2);
    int f2 = d + get_g(a, i + 1, j, c1, c2);
    f[i][j][c1][c2] = max(f1, f2);
  }
  return f[i][j][c1][c2];
}
int main() {
  ios_base::sync_with_stdio(0);
  clock_t tStart = clock();
  int tests = 1;
  for (int test = 1; test <= tests; test++) {
    cin >> n >> k;
    for (int i = 0; i < MAXN; i++) {
      for (int j = 0; j < 210; j++) {
        for (int k = 0; k < 2; k++) {
          for (int l = 0; l < 2; l++) {
            f[i][j][k][l] = -INF;
            g[i][j][k][l] = -INF;
          }
        }
      }
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    int best_dp = -INF;
    for (int j = 0; j < 2; j++) {
      best_dp = max(best_dp, get_f(a, 0, 0, 0, j));
    }
    cout << best_dp << endl;
  }
}
