#include <bits/stdc++.h>
using namespace std;
const int maxn = 30010;
const long long INF = 1e18;
int N, K;
long long a[maxn];
long long DP[maxn][205][2][2];
int main() {
  scanf("%d %d", &N, &K);
  for (int i = 1; i <= N; ++i) {
    scanf("%lld", &a[i]);
  }
  for (int j = 1; j <= K; ++j) {
    for (int x : {0, 1}) {
      for (int y : {0, 1}) {
        DP[0][j][x][y] = -INF;
      }
    }
  }
  for (int i = 1; i <= N; ++i) {
    for (int j = 1; j <= K; ++j) {
      long long c = (j > 1 && j < K) ? 2 : 1;
      DP[i][j][0][0] =
          max(DP[i - 1][j][0][0], DP[i - 1][j - 1][1][1]) - c * a[i];
      DP[i][j][1][0] =
          max(DP[i - 1][j][1][0], DP[i - 1][j - 1][0][1]) + c * a[i];
      DP[i][j][0][1] = max(DP[i - 1][j][0][1], DP[i][j][0][0]);
      DP[i][j][1][1] = max(DP[i - 1][j][1][1], DP[i][j][1][0]);
      if (c > 1) {
        DP[i][j][0][1] = max(DP[i][j][0][1], DP[i - 1][j - 1][0][1]);
        DP[i][j][1][1] = max(DP[i][j][1][1], DP[i - 1][j - 1][1][1]);
      }
    }
  }
  printf("%lld\n", max(DP[N][K][0][1], DP[N][K][1][1]));
}
