#include <bits/stdc++.h>
using namespace std;
void OpenFile() {
  freopen(
      "Subarray Cuts"
      ".INP",
      "r", stdin);
  freopen(
      "Subarray Cuts"
      ".OUT",
      "w", stdout);
}
const long long oo = (long long)1e18;
const int maxn = 3e4 + 1;
const int maxk = 2e2 + 1;
int n, k, a[maxn];
long long f[maxk][2][2][2], f2[maxk][2][2][2];
void Enter() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i];
}
void Init() {}
void Reset() {
  for (int j = 0; j <= k; ++j)
    for (int neg1 = 0; neg1 <= 1; ++neg1)
      for (int neg2 = 0; neg2 <= 1; ++neg2)
        for (int lock = 0; lock <= 1; ++lock) f2[j][neg1][neg2][lock] = -oo;
}
int Cost(int i, int j, int neg1, int neg2) {
  int res = 0;
  if (1 < j) res += neg1 * -a[i] + (neg1 ^ 1) * +a[i];
  if (j < k) res += neg2 * -a[i] + (neg2 ^ 1) * +a[i];
  return res;
}
void Max(long long &a, long long b) { a = max(a, b); }
void Solve() {
  long long res = -oo;
  for (int j = 0; j <= k; ++j)
    for (int neg1 = 0; neg1 <= 1; ++neg1)
      for (int neg2 = 0; neg2 <= 1; ++neg2)
        for (int lock = 0; lock <= 1; ++lock) f[j][neg1][neg2][lock] = -oo;
  f[1][0][0][1] = 0;
  f[1][0][1][1] = 0;
  for (int i = 0; i < n; ++i) {
    Reset();
    for (int j = 1; j <= k; ++j)
      for (int neg1 = 0; neg1 <= 1; ++neg1)
        for (int neg2 = 0; neg2 <= 1; ++neg2) {
          Max(f2[j][neg1][neg2][1], f[j][neg1][neg2][1]);
          Max(f2[j][neg1][neg2][0],
              f[j][neg1][neg2][1] + Cost(i + 1, j, neg1, neg2));
          Max(f2[j][neg1][neg2][0],
              f[j][neg1][neg2][0] + Cost(i + 1, j, neg1, neg2));
          if (j < k) {
            Max(f[j + 1][neg2 ^ 1][0][1], f[j][neg1][neg2][0]);
            Max(f[j + 1][neg2 ^ 1][1][1], f[j][neg1][neg2][0]);
          }
          if (j == k) Max(res, f2[j][neg1][neg2][0]);
        }
    swap(f, f2);
  }
  cout << res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  Enter();
  Init();
  Solve();
}
