#include <bits/stdc++.h>
using namespace std;
const int N = 40000;
const int INF = 1e9;
int a[N], s1[N][300], s2[N][300], n, m, s[N];
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    s[i] = s[i - 1] + a[i];
  }
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= m; j++) {
      s1[i][j] = -INF;
      s2[i][j] = -INF;
    }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      int ss = s[i] - s[i - j];
      s1[i][1] = max(s1[i][1], ss);
      s2[i][1] = max(s2[i][1], -ss);
    }
  }
  for (int j = 2; j <= m; j++) {
    int nows1 = -INF;
    int nows2 = -INF;
    int maxs1 = -INF;
    int maxs2 = -INF;
    for (int i = 1; i <= n; i++)
      if (j <= i) {
        if (i != 1) {
          nows1 = max(nows1, s1[i - 1][j - 1]);
          nows2 = max(nows2, s2[i - 1][j - 1]);
          maxs1 = max(maxs1, s1[i - 1][j - 1] + 2 * s[i - 1]);
          maxs2 = max(maxs2, s2[i - 1][j - 1] - 2 * s[i - 1]);
        }
        s1[i][j] = max(s1[i][j], nows1);
        s2[i][j] = max(s2[i][j], nows2);
        s1[i][j] = max(s1[i][j], maxs2 + 2 * s[i]);
        s2[i][j] = max(s2[i][j], maxs1 - 2 * s[i]);
      }
  }
  int ans = -INF;
  int nows1 = -INF;
  int nows2 = -INF;
  for (int i = 1; i <= n; i++) {
    ans = max(ans, nows1 - s[i]);
    ans = max(ans, nows2 + s[i]);
    nows1 = max(nows1, s1[i][m - 1] + s[i]);
    nows2 = max(nows2, s2[i][m - 1] - s[i]);
  }
  cout << ans << endl;
}
