#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30030;
const int MAXK = 220;
const int INF = (int)1e4 * MAXN * 3;
int DP[MAXK][MAXN][4][2];
int A[MAXN];
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> A[i];
  fill(DP[0][0][0], DP[MAXK][0][0], -INF);
  for (int j = 0; j <= n; j++)
    for (int a = 0; a < 4; a++) DP[0][j][a][0] = DP[0][j][a][1] = 0;
  for (int a = 0; a < 4; a++) DP[1][0][a][1] = 0;
  for (int i = 1; i <= k; i++)
    for (int j = 1; j <= n; j++)
      for (int a = 0; a < 4; a++) {
        int mul = (__builtin_popcount(a) - 1) * 2;
        int nb = (2 & a) ? 0 : 1;
        if (i == 1) mul = (a & 1) ? 1 : -1;
        if (i == k) mul = (a & 2) ? 1 : -1;
        DP[i][j][a][0] =
            max(DP[i][j - 1][a][0], DP[i][j - 1][a][1] + mul * A[j]);
        DP[i][j][a][1] =
            max(DP[i][j - 1][a][1] + mul * A[j],
                max(DP[i - 1][j][nb][0], DP[i - 1][j][(2 | nb)][0]));
        (void)0;
      }
  int ans = 0;
  for (int a = 0; a < 4; a++) ans = max(ans, DP[k][n][a][0]);
  cout << ans << '\n';
  return 0;
}
