#include <bits/stdc++.h>
using namespace std;
const int inf = (1 << 30) - 1;
const long long linf = (1ll << 62) - 1;
const int N = 500 + 100;
int n, k;
int a[N], s[N];
int dp[N][N], ndp[N][N];
int getSum(int l, int r) { return s[r] - (l > 0 ? s[l - 1] : 0); }
int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  s[0] = a[0];
  for (int i = 1; i < n; i++) {
    s[i] = s[i - 1] + a[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dp[i][j] = (i <= j ? 0 : -inf);
    }
  }
  for (int i = 0; i < k - 1; i++) {
    for (int j = 0; j < n; j++) {
      for (int z = j; z < n; z++) {
        ndp[j][z] = -inf;
      }
    }
    for (int j = 0; j < n; j++) {
      int dpSum = 0;
      for (int z = j; z < n; z++) {
        if (dp[j][z] == -inf) {
          continue;
        }
        dpSum += a[z];
        pair<int, int> mn(s[z], z + 1), mx(s[z], z + 1);
        for (int l = z + 1; l < n; l++) {
          ndp[mn.second][l] =
              max(ndp[mn.second][l], dp[j][z] + abs(s[l] - mn.first - dpSum));
          ndp[mx.second][l] =
              max(ndp[mx.second][l], dp[j][z] + abs(s[l] - mx.first - dpSum));
          mn = min(mn, make_pair(s[l], l + 1));
          mx = max(mx, make_pair(s[l], l + 1));
        }
      }
    }
    for (int j = 0; j < n; j++) {
      for (int z = j; z < n; z++) {
        dp[j][z] = ndp[j][z];
      }
    }
  }
  int ans = -inf;
  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      ans = max(ans, dp[i][j]);
    }
  }
  cout << ans << endl;
  return 0;
}
