#include <bits/stdc++.h>
using namespace std;
bool vis[30010][210][2][2][2];
int pd[30010][210][2][2][2];
int v[30010];
int n, K;
int solve(int ind, int cut, int s1, int s2, int tem) {
  if (cut == K) return 0LL;
  if (ind == n) return -0x3f3f3f3f;
  int &ans = pd[ind][cut][s1][s2][tem];
  if (vis[ind][cut][s1][s2][tem]) return ans;
  int p1, p2;
  if (s1)
    p1 = 1;
  else
    p1 = -1;
  if (s2)
    p2 = 1;
  else
    p2 = -1;
  if (cut == 0) p1 = 0LL;
  if (cut == K - 1) p2 = 0LL;
  vis[ind][cut][s1][s2][tem] = true;
  ans = -0x3f3f3f3f;
  int x = v[ind] * (p1 + p2);
  if (tem) {
    ans = max(x + solve(ind + 1, cut + 1, s2 ^ 1, 0, 0),
              x + solve(ind + 1, cut + 1, s2 ^ 1, 1, 0));
    ans = max(ans, x + solve(ind + 1, cut, s1, s2, tem));
  } else {
    ans = max(ans, solve(ind + 1, cut, s1, s2, 0));
    ans = max(ans, x + solve(ind + 1, cut, s1, s2, 1));
    ans = max(ans, x + solve(ind + 1, cut + 1, s2 ^ 1, 0, 0));
    ans = max(ans, x + solve(ind + 1, cut + 1, s2 ^ 1, 1, 0));
  }
  return ans;
}
int main() {
  scanf(" %d %d", &n, &K);
  for (int i = 0; i < (n); ++i) scanf(" %d", &v[i]);
  int ans = max(solve(0, 0, 0, 0, 0), solve(0, 0, 0, 1, 0));
  printf("%d\n", ans);
  return 0;
}
