#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 30 * 1000 + 10, MAX_K = 200 + 10;
int n, k, a[MAX_N], dp[MAX_N][MAX_K][2][2][2];
void read_input() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
}
int cnv(int neg) { return neg ? -1 : 1; }
void solve() {
  memset(dp, -63, sizeof dp);
  for (int(neg1) = 0; (neg1) < 2; (neg1)++)
    for (int(neg2) = 0; (neg2) < 2; (neg2)++) dp[0][1][neg1][neg2][1] = 0;
  for (int i = 0; i <= n; i++)
    for (int(neg1) = 0; (neg1) < 2; (neg1)++)
      for (int(neg2) = 0; (neg2) < 2; (neg2)++) dp[i][0][neg1][neg2][0] = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= k; j++)
      for (int(neg1) = 0; (neg1) < 2; (neg1)++)
        for (int(neg2) = 0; (neg2) < 2; (neg2)++)
          for (int(w) = 0; (w) < 2; (w)++) {
            int &r = dp[i][j][neg1][neg2][w];
            if (w)
              for (int(neg3) = 0; (neg3) < 2; (neg3)++)
                r = max(r, dp[i][j - 1][neg3][!neg1][0]);
            else
              r = max(r, dp[i - 1][j][neg1][neg2][0]);
            int x = dp[i - 1][j][neg1][neg2][1];
            if (j > 1) x += cnv(neg1) * a[i];
            if (j < k) x += cnv(neg2) * a[i];
            r = max(r, x);
          }
}
void print_output() {
  int ans = -1e9;
  for (int(neg) = 0; (neg) < 2; (neg)++) ans = max(ans, dp[n][k][neg][0][0]);
  cout << ans;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  read_input();
  solve();
  print_output();
}
