#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1000000007;
const long long BIG = 1446803456761533460;
const int Big = 336860180;
stringstream sss;
const long long int maxn = 30010;
const long long int maxk = 210;
long long int n, k;
long long int ar[maxn];
long long int dp[maxk][maxn][2][2];
void MAIN() {
  cin >> n >> k;
  for (long long int i = (0); i < (n); ++i) cin >> ar[i];
  for (long long int i = (0); i < (k); ++i)
    for (long long int j = (0); j < (n); ++j)
      for (long long int a = (0); a < (4); ++a) dp[i][j][a >> 1][a & 1] = -BIG;
  for (long long int i = (0); i < (k); ++i) {
    for (long long int j = (i); j < (n); ++j) {
      if (i == 0) {
        dp[i][j][1][0] = max(dp[i][j - 1][1][0], 0LL) - ar[j];
        dp[i][j][1][1] = max(dp[i][j - 1][1][1], 0LL) + ar[j];
      } else if (i < k - 1) {
        dp[i][j][0][0] = max(dp[i][j - 1][0][0], max(dp[i - 1][j - 1][0][0],
                                                     dp[i - 1][j - 1][1][0]));
        dp[i][j][0][1] = max(dp[i][j - 1][0][1], max(dp[i - 1][j - 1][0][1],
                                                     dp[i - 1][j - 1][1][1]));
        dp[i][j][1][0] = max(dp[i][j - 1][1][0], max(dp[i - 1][j - 1][0][1],
                                                     dp[i - 1][j - 1][1][1])) -
                         ar[j] * 2;
        dp[i][j][1][1] = max(dp[i][j - 1][1][1], max(dp[i - 1][j - 1][0][0],
                                                     dp[i - 1][j - 1][1][0])) +
                         ar[j] * 2;
      } else {
        dp[i][j][0][0] = max(dp[i][j - 1][0][0], max(dp[i - 1][j - 1][0][0],
                                                     dp[i - 1][j - 1][1][0]));
        dp[i][j][0][1] = max(dp[i][j - 1][0][1], max(dp[i - 1][j - 1][0][1],
                                                     dp[i - 1][j - 1][1][1]));
        dp[i][j][1][0] = max(dp[i][j - 1][1][0], max(dp[i - 1][j - 1][0][1],
                                                     dp[i - 1][j - 1][1][1])) -
                         ar[j];
        dp[i][j][1][1] = max(dp[i][j - 1][1][1], max(dp[i - 1][j - 1][0][0],
                                                     dp[i - 1][j - 1][1][0])) +
                         ar[j];
      }
    }
  }
  long long int ans = 0;
  for (long long int i = (0); i < (n); ++i) {
    ans = max(ans, (dp[k - 1][i][1][0]));
    ans = max(ans, (dp[k - 1][i][1][1]));
  }
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(10);
  sss << R"(
4 4
1 2 3 4
5 3
5 2 4 3 1
    )";
  MAIN();
  return 0;
}
