#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 30005;
const int MAX_K = 205;
const int inf = -1000000007;
int dp[2][MAX_K][3][3][3];
int a[MAX_N];
int n, k;
void updateMax(int &a, int b) { a = max(a, b); }
int calc(int numb, int prev, int cur, int r) {
  if (r == 0) {
    return 0;
  }
  if (numb == 1 || numb == k) {
    return (cur == 2 ? -1 : 1);
  }
  if (cur == prev) {
    return 0;
  } else {
    return (cur == 2 ? -2 : 2);
  }
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i <= 1; i++) {
    for (int j = 0; j < MAX_K; j++) {
      for (int prev = 0; prev < 3; prev++) {
        for (int cur = 0; cur < 3; cur++) {
          for (int r = 0; r < 3; r++) {
            dp[i][j][prev][cur][r] = inf;
          }
        }
      }
    }
  }
  dp[0][0][0][0][0] = 0;
  for (int i = 0; i < n; i++) {
    int now = i & 1;
    int nxt = !now;
    for (int j = 0; j <= k; j++) {
      for (int prev = 0; prev < 3; prev++) {
        for (int cur = 0; cur < 3; cur++) {
          for (int r = 0; r < 3; r++) {
            dp[nxt][j][prev][cur][r] = inf;
          }
        }
      }
    }
    for (int j = 0; j <= k; j++) {
      for (int prev = 0; prev < 3; prev++) {
        for (int cur = 0; cur < 3; cur++) {
          for (int r = 0; r < 3; r++) {
            if (dp[now][j][prev][cur][r] == inf) {
              continue;
            }
            int curVal = dp[now][j][prev][cur][r];
            updateMax(dp[nxt][j][prev][cur][r],
                      curVal + calc(j, prev, cur, r) * a[i + 1]);
            if (r != 0) {
              updateMax(dp[nxt][j][prev][cur][0], curVal);
            }
            if (j + 1 < k) {
              updateMax(dp[nxt][j + 1][cur][1][1],
                        curVal + calc(j + 1, cur, 1, 1) * a[i + 1]);
              updateMax(dp[nxt][j + 1][cur][2][2],
                        curVal + calc(j + 1, cur, 2, 2) * a[i + 1]);
            } else {
              updateMax(dp[nxt][j + 1][cur][3 - cur][3 - cur],
                        curVal + calc(j + 1, cur, 3 - cur, 3 - cur) * a[i + 1]);
            }
          }
        }
      }
    }
  }
  int res = inf;
  for (int prev = 0; prev < 3; prev++) {
    for (int cur = 0; cur < 3; cur++) {
      for (int r = 0; r < 3; r++) {
        updateMax(res, dp[n & 1][k][prev][cur][r]);
      }
    }
  }
  cout << res;
  return 0;
}
