#include <bits/stdc++.h>
using namespace std;
const int maxN = 3e4 + 10;
int n, k, f[maxN][222][4];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= k; ++i)
    for (int j = 0; j < 4; ++j) f[0][i][j] = -1e9 - 10;
  for (int i = 1; i <= n; ++i) {
    int a;
    cin >> a;
    for (int j = 1; j <= k; ++j) {
      int r = 2 - (j == 1 || j == k);
      f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j - 1][3]) - r * a;
      f[i][j][1] = max(f[i - 1][j][1], f[i][j][0]);
      f[i][j][2] = max(f[i - 1][j][2], f[i - 1][j - 1][1]) + r * a;
      f[i][j][3] = max(f[i - 1][j][3], f[i][j][2]);
      if (r - 1) {
        f[i][j][1] = max(f[i][j][1], f[i - 1][j - 1][1]);
        f[i][j][3] = max(f[i][j][3], f[i - 1][j - 1][3]);
      }
    }
  }
  cout << max(f[n][k][1], f[n][k][3]);
}
