#include <bits/stdc++.h>
using namespace std;
long long DP[400][400];
long long A[401];
long long PS[401];
long long AP[401];
long long AM[401];
bool V[401];
int main() {
  int N;
  cin >> N;
  int K;
  cin >> K;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    PS[i] = A[i];
    if (i) PS[i] += PS[i - 1];
  }
  for (int i = 0; i < (int)N; i++) {
    AP[i] = -1000000000000000ll;
    AM[i] = -1000000000000000ll;
  }
  K--;
  for (int i = 0; i < N; i++)
    for (int j = i; j < N; j++) {
      long long S1 = PS[j] - (i > 0 ? PS[i - 1] : 0);
      AP[j] = max(AP[j], S1);
      AM[j] = max(AM[j], -S1);
    }
  int c = 0;
  while (K--) {
    memset(V, 0, sizeof(V));
    c++;
    for (int i = N - 1; i >= 0; i--) {
      for (int j = i; j < N; j++) {
        if (i < c)
          DP[i][j] = -1000000000000000ll;
        else {
          DP[i][j] = 0;
          long long S1 = PS[j] - (i > 0 ? PS[i - 1] : 0);
          for (int k = 0; k < i; k++) {
            DP[i][j] = max(DP[i][j], AP[k] - S1);
            DP[i][j] = max(DP[i][j], S1 + AM[k]);
          }
          if (V[j] == 0) {
            V[j] = true;
            AP[j] = DP[i][j] + S1;
            AM[j] = DP[i][j] - S1;
          }
          AP[j] = max(AP[j], DP[i][j] + S1);
          AM[j] = max(AM[j], DP[i][j] - S1);
        }
      }
    }
  }
  long long tp = -1000000000000000ll;
  for (int i = 0; i < N; i++)
    for (int j = i; j < N; j++) tp = max(tp, DP[i][j]);
  cout << tp << endl;
  return 0;
}
