#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e4 + 12, MAX_K = 2e2 + 4, inf = 1e9 + 7;
int n, k, ans;
int Arr[MAX_N];
int psum[MAX_N];
int dp[MAX_N][MAX_K][4];
int one[4];
int main() {
  one[0] = 0, one[1] = one[2] = 1, one[3] = 2;
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> Arr[i];
  if (k == 1) {
    cout << "0\n";
    return 0;
  }
  for (int i = 1; i <= k; i++)
    for (int mask = 0; mask < 4; mask++) dp[0][i][mask] = -inf;
  int mn = 0, mx = 0;
  for (int i = 1; i <= n; i++) {
    mn += Arr[i];
    if (Arr[i] <= mn) mn = Arr[i];
    mx += Arr[i];
    if (mx <= Arr[i]) mx = Arr[i];
    dp[i][1][0] = dp[i][1][2] = mx;
    dp[i][1][1] = dp[i][1][3] = -mn;
    for (int j = 2; j <= k; j++)
      for (int mask = 0; mask < 4; mask++) {
        dp[i][j][mask] = Arr[i] * (2 - 2 * one[mask]);
        dp[i][j][mask] +=
            max({dp[i - 1][j][mask], dp[i - 1][j - 1][1 - (mask >> 1)],
                 dp[i - 1][j - 1][3 - (mask >> 1)]});
      }
  }
  mx = 0, mn = 0;
  for (int i = n; 1 < i; i--) {
    mn += Arr[i];
    if (Arr[i] <= mn) mn = Arr[i];
    mx += Arr[i];
    if (mx <= Arr[i]) mx = Arr[i];
    ans = max(ans, dp[i - 1][k - 1][0] - mn);
    ans = max(ans, dp[i - 1][k - 1][2] - mn);
    ans = max(ans, dp[i - 1][k - 1][1] + mx);
    ans = max(ans, dp[i - 1][k - 1][3] + mx);
  }
  cout << ans << "\n";
  return 0;
}
