#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 30030;
const int K = 220;
int n, k;
long long a[N];
long long dp[N][K][2], s[N];
long long max[N], min[N];
const long long inf = 1e18;
inline void up(long long& x, long long y) {
  if (x < y) x = y;
}
int main() {
  std::ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> k;
  for (int i = (1), iend = (n); i <= iend; ++i)
    cin >> a[i], s[i] = s[i - 1] + a[i];
  for (int i = (0), iend = (n); i <= iend; ++i)
    for (int j = (1), jend = (k); j <= jend; ++j)
      for (int k = (0), kend = (1); k <= kend; ++k) dp[i][j][k] = -inf;
  for (int i = 1; i <= n; ++i) {
    max[i] = std::max<long long>(max[i - 1], 0) + a[i];
    min[i] = std::min<long long>(min[i - 1], 0) + a[i];
  }
  for (int i = (1), iend = (n); i <= iend; ++i) {
    dp[i][1][0] = -min[i];
    dp[i][1][1] = max[i];
  }
  for (int i = (1), iend = (n); i <= iend; ++i) {
    for (int l = (2), lend = (k - 1); l <= lend; ++l) {
      up(dp[i][l][0], dp[i - 1][l][0]);
      up(dp[i][l][1], dp[i - 1][l][1]);
      for (int j = (1), jend = (i); j <= jend; ++j) {
        up(dp[i][l][0],
           dp[j - 1][l - 1][0] + (s[i] - s[j - 1]) - (s[i] - s[j - 1]));
        up(dp[i][l][0],
           dp[j - 1][l - 1][1] - (s[i] - s[j - 1]) - (s[i] - s[j - 1]));
        up(dp[i][l][1],
           dp[j - 1][l - 1][0] + (s[i] - s[j - 1]) + (s[i] - s[j - 1]));
        up(dp[i][l][1],
           dp[j - 1][l - 1][1] - (s[i] - s[j - 1]) + (s[i] - s[j - 1]));
      }
    }
  }
  long long res = 0;
  std::reverse(a + 1, a + n + 1);
  for (int i = (1), iend = (n); i <= iend; ++i) {
    max[i] = std::max<long long>(max[i - 1], 0) + a[i];
    min[i] = std::min<long long>(min[i - 1], 0) + a[i];
  }
  std::reverse(a + 1, a + n + 1);
  std::reverse(max + 1, max + n + 1);
  std::reverse(min + 1, min + n + 1);
  for (int i = (1), iend = (n); i <= iend; ++i) {
    up(res, dp[i - 1][k - 1][0] + max[i]);
    up(res, dp[i - 1][k - 1][1] - min[i]);
  }
  cout << res << '\n';
}
